
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[runningheads,a4paper]{llncs}



\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}


\usepackage{bm}% bold math
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{epsfig}
\usepackage{amsbsy}
\usepackage{array}
\usepackage{setspace}
\usepackage{slashbox}
\usepackage{ctable, dashrule}
\usepackage{color}

\usepackage{caption}
\captionsetup{font={scriptsize}}

%{\noindent \(\Box\)\par\addvspace{\medskipamount}}

\renewenvironment{proof}{\addvspace{\medskipamount}\noindent{\em Proof. }}%
{\rightline { $\Box$ }\par\addvspace{\medskipamount}}

\usepackage{arydshln}

% \renewcommand{\arraystretch}{1.8}


\newcommand{\tablepage}[2]{\begin{minipage}{#1}\vspace{0.5ex} #2 \vspace{0.5ex}\end{minipage}}
\newcommand{\ignore}[1]{}
\newcommand{\eps}{\varepsilon}
\newcommand{\R}{\mathcal{R}}
\newcommand{\weak}{\mathcal{W}eak}
\newcommand{\block}{\mathcal{B}lock}
\newcommand{\sv}{\mathcal{SV}}
\newcommand{\bcl}{\mathcal{BCL}}
\newcommand{\Ext}{\textsf{Enc}}
%\mathsf{Ext}}
\newcommand{\Enc}{\textsf{Enc}}
\newcommand{\sd}{\textsf{SD}}
\newcommand{\rd}{\textsf{RD}}
\newcommand{\bit}{\{0,1\}}
\newcommand{\br}{\mathbf{r}}

\newcommand{\supp}{\mathop{\mbox{supp}}}


\usepackage{cite}
\def\citeBreaks{\do\A\do\[\do\\\do\]\do\^}


\usepackage{url}



\usepackage[T1]{fontenc}
\usepackage{subfig}

\captionsetup{belowskip=-20pt,aboveskip=-20pt}

\urldef{\mailsa}\path|dodis@cs.nyu.edu|
\urldef{\mailsb}\path|yaoyanqing1984@gmail.com|

\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}





\begin{document}

\mainmatter  % start of an individual contribution

% first the title is needed
\title{Privacy with Imperfect Randomness}

% a short form should be given in case it is too long for the running head
\titlerunning{Privacy with Imperfect Randomness}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Yevgeniy Dodis$^1$  and   Yanqing Yao$^2$   \footnote{  Most of this work was done while the author visited New York University.  } }
%
\authorrunning{     }
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
\institute{ $^1$  Department of Computer Science, New York University, New York, USA \\
\mailsa\\
$^2$  School of Computer Science and Engineering,    Beihang University, Beijing, China \\
\mailsb\\
}

%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle

\vspace{-5mm}
\begin{abstract}


We revisit the impossibility of a variety of cryptographic tasks
including privacy and differential privacy with imperfect randomness.
For traditional notions of privacy, such as security of encryption,
commitment or secret sharing schemes, dramatic impossibility results
are known~\cite{MP90,DOPS04} for several concrete sources $\mathcal{R}$, including
a (seemingly) very ``nice and friendly'' Santha-Vazirani (SV) source.
%The SV source outputs a
%sequence of bits $r_1,r_2,\ldots$, where each $r_i$ has almost 1 full
%bit of fresh entropy conditioned on the previous bits $r_1,\ldots,r_{i-1}$.
%
\ignore{
Moreover, Bosley and Dodis
\cite{BD07} gave strong evidence that many traditional privacy tasks
(e.g., encryption) inherently require an ``extractable'' source of
randomness.

\vspace{1ex}
The common interpretation of these
negative results is that privacy is impossible even with
``very structured'' imperfect sources.
}
%
Somewhat surprisingly, Dodis et al.~\cite{DLMV12}
%put a slight dent in this belief, by showing
showed that non-trivial {\em differential}
privacy is possible with the SV sources. This suggested a qualitative gap between
traditional and differential privacy, and left open the question of whether
differential privacy is possible with more realistic (i.e., less
structured) sources than the SV sources.

\vspace{1ex}
Motivated by this question, we introduce a new, modular framework
for showing strong impossibility results for (both traditional and differential)
privacy under a {\em general} imperfect source $\mathcal{R}$.
%
\ignore{
In particular, we introduce natural and easy-to-understand concepts of  {\em expressiveness} and {\em separability} of a given imperfect source $\mathcal{R}$,
%as a measure of its ``imperfectness'',
and show the following results:

\begin{itemize}
\item Low levels of expressiveness generically imply strong impossibility
results for both traditional and {\em differential} privacy.
\item Separability implies expressiveness; NON-separability is equivalent to ``weak bit extraction''.
\item While the separability of some concrete (e.g., SV) sources $\mathcal{R}$ was implicitly known, we show new separability results for several important sources, including general ``block sources''.
\end{itemize}

As direct corollaries of these {\em general} results, we get the following corollaries:
}
As direct corollaries of our framework, we get the following new results:

%
\begin{itemize}
\item[(1)] Existing, but {\em quantitatively improved}, impossibility results for traditional privacy, but under a wider variety of sources $\mathcal{R}$.
\item[(2)] First impossibility results for {\em differential} privacy for a variety of realistic sources $\R$ (including most ``block sources'', but not the SV source).
% Although, unsurprisingly, these results  (barely) miss the highly structured SV sources, %they  come back {\em extremely quickly} once the source becomes slightly more realistic %(e.g., a realistic ``block source'').
\item[(3)] Any imperfect source allowing (either traditional or differential) privacy under $\R$ admits a
certain type of deterministic bit extraction from $\R$.
%: (a) when produced, the extracted bit is
%guaranteed to be almost unbiased, (b) although the extractor is
%allowed to fail, it will typically succeed at least on the uniform
%distribution.
%(This result is incomparable to the result of~\cite{BD07}.)
\end{itemize}

\ignore{
Overall,
our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with {\em general} imperfect sources.
}




%\keywords{ imperfect randomness, entropy sources,  Santha-Vazirani sources, block sources, %Bias-Control Limited sources, randomness extraction, privacy, differential privacy   }
\end{abstract}

\newcommand{\mypar}[1]{\vspace{4pt} \noindent {\sc #1}\ }


\section{Introduction}


Traditional cryptographic
tasks take for granted the availability of perfect random sources, i.e., sources that output unbiased and independent
random bits. However, in many situations  it seems unrealistic to expect a source to be perfectly random, and one must deal with various imperfect sources of randomness. Some well known
examples of such imperfect random sources are
physical sources \cite{BST03,BH05}, biometric data \cite{BDK$^+$05,DORS08},
secrets with partial leakage, and group elements from Diffie-Hellman key exchange \cite{GKR04,K10}.

\mypar{Imperfect Sources.} To abstract this concept, several formal models of  imperfect sources have been described (e.g., \citeBreaks{[vN51,CFG$^+$85,B86,SV86,CG88,LLS89,Z-\\uc96,ACRT99,D01]}). Roughly, they can be divided into extractable and non-extractable. Extractable sources (e.g., \cite{vN51,CFG$^+$85,B86,LLS89}) allow for deterministic extraction of nearly perfect randomness. And, while the question of optimizing the extraction rate and efficiency has been very interesting, from the qualitative perspective such sources are good for any application where perfect randomness is sufficient. Unfortunately,  it was quickly realized many imperfect sources are non-extractable~\cite{SV86,CG88,D01}. The simplest example  is  the Santha-Vazirani (SV) source~\cite{SV86}, which produces an infinite sequence of  bits $r_1, r_2,  \hdots$, with the property
that $\Pr[r_i=0\mid r_1\ldots r_{i-1}] \in [\frac{1}{2} ( 1 - \gamma), \frac{1}{2} ( 1 + \gamma)]$, for any setting of the prior bits $r_1,  \ldots, r_{i-1}$. Namely, each bit has almost one bit of fresh entropy, but can have a
small bias $\gamma <  1$.  Santha and Vazirani~\cite{SV86} showed that there exists no deterministic
extractor $\Ext: \bit^n\rightarrow \bit$ capable of extracting even a {\em single} bit of bias {\em strictly} less than $\gamma$ from the $\gamma$-SV source, irrespective of how many SV bits $r_1,  \ldots, r_n$ it is willing to wait for.

Despite this pessimistic result, ruling out the ``black-box compiler'' from imperfect (e.g., SV) to  perfect randomness for {\em all} applications, one may still hope that specific ``non-extractable'' sources, such as SV-sources, might  be sufficient for {\em concrete} applications, such as simulating probabilistic algorithms or cryptography. Indeed, a series of results~\cite{VV85,SV86,CG88,Zuc96,ACRT99} showed that very ``weak'' sources
(including SV-sources and even much more realistic ``weak'' and ``block'' sources) are sufficient for simulating probabilistic polynomial-time
algorithms; namely, for problems which do not inherently need randomness, but which could potentially
be sped up using randomization. Moreover, even in the area of cryptography --- where randomness is {\em essential} (e.g., for key generation) --- it turns out that many ``non-extractable''  sources (again, including SV sources and more) are sufficient for {\em authentication} applications, such as the designs of MACs~\cite{MW97,DKRS06} and even signature schemes~\cite{DOPS04,ACMPS14} (under appropriate hardness assumptions). Intuitively, the reason for the latter ``success story'' is that authentication applications only require that it is hard for the attacker to completely guess (i.e., ``forge'') some long string, so having min-entropy in our source should be sufficient to achieve this goal.

\mypar{Negative Results for Privacy with Imperfect Randomness.} In contrast, the situation appears to be much less bright when dealing with {\em privacy} applications, such as encryption, commitment, zero-knowledge, and a few others. First, McInnes and Pinkas~\cite{MP90} showed that unconditionally secure symmetric encryption cannot be based on SV sources, even if one is restricted to encrypting a single bit. This result was subsequently strengthened by Dodis et al.~\cite{DOPS04}, who showed that SV sources are not sufficient for building even computationally secure encryption (again, even of a single bit), and, in fact, essentially any other cryptographic task involving ``privacy'' (e.g.,   commitment, zero-knowledge, secret sharing and others). This was again strengthened by Austrin et al.~\cite{ACMPS14}, who showed that the negative results still hold even if the SV source is efficiently samplable. Finally, Bosley and Dodis~\cite{BD07} showed an even more negative result: if a source of randomness $\R$ is ``good enough'' to generate a secret key capable of encrypting $k$ bits, then one can deterministically extract nearly $k$ almost uniform bits from $\R$, suggesting that traditional privacy {\em requires} an ``extractable'' source of randomness.\footnote{On the positive side,~\cite{DS02} and \cite{BD07} showed that extractable sources are not strictly necessary for encrypting a ``very small'' number of bits. Still, for natural ``non-extractable'' sources, such as SV sources, it is known that encrypting even a single bit is impossible~\cite{SV86,DOPS04,ACMPS14}.}

\mypar{What about Differential Privacy?}
While the above series of negative results seem to strongly point in the direction that privacy inherently requires extractable randomness, a recent work of Dodis et al.~\cite{DLMV12} put a slight dent into this consensus, by showing that SV sources are provably sufficient for achieving a more recent notion of privacy, called {\em differential privacy}~\cite{DMNS06}. Intuitively, a differentially private mechanism $M(D, \br)$ uses its randomness $\br$ to add some ``noise'' to the true answer $q(D)$, where $D$ is some sensitive database of users, and $q$ is some useful aggregate information (query) about the users of $D$. This noise is added in a way as to satisfy the following two conflicting properties   (see Definitions~\ref{dp} and~\ref{uti} for formalism):
\begin{itemize}

\item[(a)] {\em $\eps$-differential privacy} ($\eps$-DP): up to ``advantage'' $\eps$, the returned value $z = M(D, \br)$ does not tell any information about the value $D(i)$ of any individual user $i$, which was not already known to the attacker before $z$ was returned;

\item[(b)] {\em $\rho$-utility}: on average (over $\br$), $|z-q(D)|$ is upper bounded by $\rho$, meaning that perturbed answer is not too far from the true answer.

\end{itemize}
%
Since we will be mainly talking about negative results, for the rest of this work we will restrict our attention to the simplest concrete example of differential privacy, where a ``record'' $D(i)$ is a single bit, and $q$ is the Hamming weight $wt(D)$ of the corresponding bit-vector $D$ (i.e., $wt(D) = \sum D(i)$). In this case, a very simple $\eps$-DP mechanism~\cite{DMNS06}  $M(D,\br)$ would simply return $wt(D)+e(\br)$ (possibly truncated to always be between $0$ and $|D|$), where $e(\br)$ is an appropriate noise\footnote{So called Laplacian distribution, but the details do not matter here.} with $\rho= \mathbb{E}[|q(\br)|] \approx 1/\eps$. Intuitively, this setting ensures that when $D(i)$ changes from $0$ to $1$, the answer distribution $M(D, \br)$ does not ``change'' by more than $\eps$.

Coming back to Dodis et al.~\cite{DLMV12}, the authors show that although no ``additive noise'' mechanism
of the form $M(D,\br) = wt(D)+e(\br)$ can simultaneously withstand all $\gamma$-SV-distributions $\br\leftarrow R$, a better designed mechanism (that they also constructed) is capable of working with all such distributions, provided that the utility $\rho$ is now relaxed to be polynomial in $1/\eps$, whose degree and coefficients depend on $\gamma$, but {\em not} on the size of the database $D$.
Moreover, {\em the value $\eps$ can be made an arbitrarily small constant} (e.g., $\eps\ll \gamma$).
This should be contrasted with the impossibility results for the traditional privacy~\cite{MP90,DOPS04} with SV sources, where it was shown that $\eps=\Omega(\gamma)$, meaning that even a fixed {\em constant} (let alone ``negligible'') security is impossible. Hence, the result of \cite{DLMV12} suggested a {\em qualitative gap between traditional and differential privacy},
%\footnote{At first, such gap might appear unsurprising, since traditional privacy usually demands %``negligible'' security $\eps$, while differential privacy clearly {\em cannot} achieve such negligible %$\eps$ with any ``non-negligible'' utility $\rho$. As we mentioned, however, traditional privacy with SV %sources is impossible even for {\em constant} $\eps$.}
but left open the question of whether differential privacy is possible with more realistic (i.e., less structured) sources than the  SV sources. Indeed, the SV sources seem to be primarily interesting from the perspective of negative results, since real-world distributions are unlikely to produce a sequence of bits, each of which has almost a full unit of fresh entropy.

\mypar{Our Results In Brief.} In part motivated by solving this question, we abstract and generalize
prior techniques for showing impossibility results for achieving privacy with various imperfect sources of randomness. Unlike prior work (with the exception of~\cite{BD07}), which focused on specific imperfect sources $\R$ (e.g., SV sources), we obtain most of our results for {\em general} sources $\R$, but then use various natural sources (namely, SV sources~\cite{SV86}, weak/block sources~\cite{CG88}, and Bias-Control Limited sources~\cite{D01}) as specific examples to illustrate our technique. In particular, we introduce the concepts of {\em expressiveness} and {\em separability} of a given imperfect source $\R$ as a measure of its ``imperfectness'', and show the following results:

\begin{itemize}
\item Low levels of expressiveness generically imply strong impossibility
results for   {\em differential} as well as traditional privacy.
\item  We reduce expressiveness to separability and prove the equivalence between ``weak bit extraction'' and  NON-separability.
\item Though the separability of some concrete (e.g., SV) sources $\mathcal{R}$ was implicitly known, we show new separability results for several important sources, including general ``block sources''.
\end{itemize}

We stress that the first two results are completely generic, and reduce the question of feasibility of privacy under $\mathcal{R}$ to a much easier and self-contained question of separability of $\mathcal{R}$. And establishing the latter is the only ``source-specific'' technical work which remains. In particular, after explicitly stating known separability results for weak  and SV  sources, and establishing our new separability results for block and  Bias-Control Limited (BCL)  sources, we obtain the following direct corollaries:

%As direct corollaries of these {\em general} results, we get the following corollaries:

\begin{itemize}
\item Existing, but {\em quantitatively improved}, impossibility results for traditional privacy, but under a wider variety of sources $\mathcal{R}$ (i.e., weak, block, SV, BCL).
\item First impossibility results for {\em differential} privacy. Although, unsurprisingly, these results  (barely) miss the highly structured SV sources, they  come back {\em extremely quickly} once the source becomes slightly more realistic (e.g., a very ``constrained'' weak/block/BCL source).
\item Any imperfect source allowing (either traditional or differential) privacy admits a
certain type of deterministic bit extraction.
%: (a) when produced, the extracted bit is
%guaranteed to be almost unbiased, (b) although the extractor is
%allowed to fail, it will typically succeed at least on the uniform
%distribution.
(This result is incomparable to the result of~\cite{BD07}.)
\end{itemize}

We briefly expand on these results below, but conclude that, despite the result of ~\cite{DLMV12}, our results seem to unify and strengthen the belief that, for the most part,  privacy with imperfect randomness is impossible, unless the source is (almost) deterministically extractable. More importantly, they provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with {\em general} imperfect sources.

\subsection{Our Results in More Detail}

At a high level, our results follow the blueprint of~\cite{DOPS04} (who concentrated exclusively on the SV sources), but in significantly more modular and quantitatively optimized way (making our proofs somewhat more illuminating, in our opinion). In essence, they establish an impossibility of a given privacy task $P$ under a source ${\mathcal R}$ using three steps:

\mypar{\underline{Step 1: impossibility of task $P$ under $\R$ $\longrightarrow$ expressiveness of ${\mathcal R}$}.} \\
 Intuitively, {\em expressiveness}  of $\R$ means that $\R$ is rich enough to ``distinguish'' any functions $f$ and $g$ which are not point-wise equal almost everywhere (see Definition~\ref{exp}): there exists $R\in \R$ s.t. $\sd(f(R),g(R))$ is ``noticeable'', where $\sd$ is the statistical distance between distributions.\footnote{Like in \cite{DOPS04} and unlike \cite{MP90}, our distinguishers between $f(R)$ and $g(R)$ will be very efficient, but we will not require this in order not to clutter the notation.}
%Using the ideas of \cite{DOPS04},
With this clean abstraction, we almost trivially show (see Theorem~\ref{expp}) that most traditional privacy tasks $P$ (extraction, encryption, secret sharing, commitment) imply the existence of sufficiently-distinct functions $f$ and $g$ that violate the expressiveness of $\R$. For example, such $f(\br)$ and $g(\br)$ are simply the encryptions of two different plaintexts under key $\br$ when $P$ is encryption, and similar arguments hold for commitment, extraction and secret sharing schemes.

More interestingly,
%despite the positive result of \cite{DLMV12} regarding the SV sources,
we show expressiveness  is again sufficient to rule out even {\em differential} privacy (Theorem~\ref{imdp}). The proof follows the same high-level intuition as for the traditional privacy, but is somewhat more involved. This is because DP only gives us security for ``close'' databases, while the utility guarantees are only meaningful for ``far'' databases. In particular, for this reason it will turn out that the expressiveness  requirement on $\R$ for ruling out differential privacy will be slightly higher than that for traditional privacy (Theorem~\ref{imdp} vs. Theorem~\ref{expp}).\footnote{Jumping ahead, this will be the reason although our new impossibility results for DP will (barely) miss the SV sources, they will come back very quickly once the source becomes more realistic.} Still, aside from this quantitative difference, there is no qualitative difference between our arguments for traditional and differential privacy.

Overall, the deceptive simplicity of our ``privacy-to-expressiveness'' arguments is actually a {\em feature} of our framework, as these arguments are the {\em only place when the specific details of $P$ matter}, as the rest of the framework --- described below ---  will only concentrate on the expressiveness of $\R$!

\mypar{\underline{Step 2: expressiveness of ${\mathcal R}$ $\longrightarrow$ separability of ${\mathcal R}$}.} \\
Intuitively, {\em separability} of $\R$ means that $\R$ is rich enough to ``separate'' any sufficiently large disjoint sets $G$ and $B$ (see Definition~\ref{sep}; wlog, assume that $|G|\ge |B|$): there exists $R\in \R$ s.t. $(\Pr[R\in G] - \Pr[R\in B])$ is ``noticeable''.\footnote{For example, if $\R$ only consists of the uniform distribution $U_n$, the latter is impossible when $|G|=|B|$. In contrast, we will see that  natural ``non-extractable'' sources (i.e., weak, block, SV, and BCL sources)  are separable.}
A moment reflection shows that separability is closely related to expressiveness, but restricted to {\em  boolean} functions $f$ and $g$ of disjoint support (i.e., the characteristic functions of $G$ and $B$), which makes it noticeably easier to work with (as we will see).

Nevertheless, we show that {\em separability generically implies expressiveness}, with nearly identical parameters (see Theorem~\ref{theorem1}). This is where we differ and quantitatively improve the argument implicit in~\cite{DOPS04}: while \cite{DOPS04} used a bit-by-bit hybrid argument to show expressiveness  (for the SV source), our proof of Theorem~\ref{theorem1} used a more clever ``universal hashing trick'', \footnote{Similar trick with randomness extractors was used, in a slightly different context, by~\cite{ACMPS14}.}  allowing us to obtain results which are independent of the ranges of $f$ and $g$ (which, in turn, will later correspond to bit sizes of ciphertexts, commitments, secret shares, etc.)
%As a consequence, we get simple and elegant expressiveness  statements for a variety of natural sources %(Corollary~\ref{spee}).

Of independent interest, we also show that  NON-separability of $\R$ is equivalent to some type of ``weak bit extraction'' from $\R$ (see Theorem~\ref{implies-ext}): (a) when produced, the extracted bit is
guaranteed to be almost unbiased, (b) although the extractor is allowed to fail, it will typically succeed at least on the uniform distribution.\footnote{Unfortunately, we demonstrate that the limitation of part (b) holding only for the uniform distribution is somewhat inherent {\em in this great level of generality}.}
%This result is similar in spirit, but incomparable to the result
%of Bosley and Dodis~\cite{BD07}.

Coupled with Step 1, we get the following two implications. First, we reduce the impossibility of many privacy tasks $P$ under $\R$ to a much easier question of separability of $\R$ (which is independent of $P$). Second, we generically show that the feasibility of $P$ under $\R$ implies deterministic weak bit extraction from $\R$, incomparably complementing the prior result of \cite{BD07}.
Namely, \cite{BD07} showed that several traditional privacy primitives, including (only multi-bit) encryption and commitment (but not secret sharing) imply the existence of multi-bit deterministic extraction schemes capable of extracting almost the same number of bits as the plaintext. On the positive, our result applies to a much wider set of primitives $P$ (e.g., secret-sharing, as well as even {\em single-bit} encryption and commitment). On the negative, we can only argue a rather weak kind of single-bit extraction, where the extractor is allowed to fail, while  \cite{BD07} showed traditional, and possibly multi-bit, extraction.

%And all these implications are obtained without using any specific details of our source $\R$!

\mypar{\underline{Step 3: separability of various sources ${\mathcal R}$}.} \\
 Unlike the prior results in~\cite{MP90,DOPS04,ACMPS14}, all the above results are true for any imperfect source $\R$. To get concrete impossibility results for natural sources, though, we finally must establish good separability bounds for specific $\R$. Such bounds were already implicitly known~\cite{DOPS04} (or trivial to see) for the SV and general weak sources, but we show how they can also be demonstrated for other natural sources: block sources~\cite{CG88} and Bias-Control Limited  sources~\cite{D01}. In particular, our separability bounds for block sources turned out to be quite non-trivial, and form one of the more technical contributions of this work. See the proof of Lemma~\ref{lemma3}(b).

Aside from being natural and interesting in their own right, the new separability results for block/BCL  sources are especially interesting from the perspective of differential privacy (see below). Indeed, both of them can be viewed as realistic relaxations of highly-structured (and unrealistic!) SV sources, but yet not as general/unstructured as weak sources. And since we already know that DP {\em is} possible with SV sources~\cite{DLMV12}, it is interesting to know how soon it will take for the impossibility results to come back, once the source slowly becomes more realistic/unstructured, but before going ``all the way'' to being weak.

\mypar{Putting them all together: New and Old Impossibility Results.}
Applying Steps 1-3 to specific sources of interest (i.e., weak, block, SV, and BCL sources), we immediately derive a variety of impossibility results for traditional privacy (see Table~\ref{table1}). Although these results were derived mainly as a ``warm-up'' to our (completely new) impossibility results for differentially privacy, they offer quantitative improvements to the results of \cite{DOPS04} (due to stronger expressiveness-to-separability reduction). For example, they rule out even constant (as opposed to negligible) security for encryption/commitment/secret sharing, irrespective of the sizes of ciphertexts/commitments/shares. Relatedly, we unsurprisingly get stronger impossibility results for block/BCL sources than the more structured SV sources.

%, and also allow immediate applications to other imperfect sources. For instance, we get the following new %result for BCL sources: even constant security $1/2$ for traditional privacy is impossible to achieve when %the number of interventions $b = \Omega(1/\gamma)$. More importantly, instead of focusing the entire proof %on some specific weak/block/SV sources~\cite{MP90,DOPS04}, our privacy impossibility results for such %sources were obtained in a more modular manner, making these proofs somewhat more illuminating.

More interestingly, we obtain first impossibility results for differential privacy with imperfect randomness. In light of the positive result of \cite{DLMV12}, our separability result for SV sources is (barely) not strong enough to rule out differential privacy under SV sources. As we explained, this failure happened not because our framework was too weak to apply to SV sources or differential privacy, but rather due to a ``local-vs-global gap'' between the privacy and utility requirements for differential privacy.

However, once we consider general weak sources, or even much more structured BCL/block sources, the impossibility results come back {\em extremely quickly}! For example, when studying $\eps$-DP with utility $\rho$, $n$-bit weak sources of min-entropy $k$ are ruled out the moment $k = n- \log(\eps \rho) -O(1)$ (Theorem~\ref{weak-imp,block-imp,bcl-imp}(a)),\footnote{More generally, even $n$-bit block sources with block length $m$ and fresh min-entropy $k$ per block are ruled out when $k = m- \log(\eps \rho) -O(1)$, irrespective of the number of blocks $n/m$. See Theorem~\ref{weak-imp,block-imp,bcl-imp}(b).} while BCL sources are ruled out the moment the number of ``SV bits'' $b$ the attacker can fix completely (instead of only bias by $\gamma$) is just $b = \Omega(\log(\eps \rho)/\gamma)$ (Theorem~\ref{weak-imp,block-imp,bcl-imp}(c)). As $\eps \rho$ is typically desired to be a constant, $\log(\eps \rho)$ is an even smaller constant, which means we even rule out {\em constant} entropy deficiency  $(n-k)$ (or $m-k$ for block source) or number of ``interventions'' $b$, respectively.  We also compare impossibility results for traditional and differential privacy in Table~\ref{table2}, and observe that the latter
%impossibility results
are only marginally weaker than the former. This leads us to the conclusion that differential privacy is still rather demanding to achieve with realistic imperfect sources of randomness.
%
%Overall, we believe our results provide an intuitive, modular and unified picture %elucidating the (im)possibility of privacy with {\em general} imperfect sources.

\ignore{

In particular, we concentrate on the Bias-Control Limited (BCL) source of Dodis~\cite{D01}.  The BCL source  generates
$n$ bits $r_1, r_2, \ldots,  r_n$, where for $i =1, 2, \ldots, n$, the value  of $r_i$
can depend on  $r_1, r_2, \ldots,  r_{i-1}$ in one of the following two ways: (A) $r_i$ is determined by $r_1, r_2, \ldots, r_{i-1}$, but this happens for at most $b$ bits, or (B) $  \frac{1-  \gamma}{2}  \leq   \Pr[r_i=1 \mid r_1  r_2 \ldots r_{i-1}]  \leq \frac{1+ \gamma}{2}$.   In particular, when
$b=0$, it degenerates into the $\gamma$-SV source~\cite{SV86}; when $\gamma =0$, it yields the $b$-sequential-bit-fixing source of  Lichtenstein, Linial, and Saks \cite{LLS89}.
 The BCL source models the setting that each of the bits produced by a
realistic streaming source is unlikely to be perfectly random: slight errors
%(due to noise, measurement errors, and imperfections)
of the source are inevitable almost always,  and, rarely, some of the bits could have non-trivial dependencies on the previous bits,
%(due to internal correlations, poor measurement or improper setup),
to the point of being completely determined by them. Hence, the  BCL source appears much more realistic than the SV source, especially if the number of interventions $b$ is somewhat moderate.
From our perspective, the BCL source will be especially interesting when we deal with differential privacy. Indeed, since it naturally (and realistically!) relaxes the SV source, for which non-trivial differential privacy is possible, it will be interesting to see the minimal value of $b$
%(number of interventions)
when the impossibility results come back.

Returning to our results, after showing simple separability claims for weak, block, SV and BCL sources  (see Lemma~\ref{lemma3}), we define the notion of expressiveness.

Intuitively, expressiveness  of $\R$ means that $\R$ is rich enough to ``distinguish'' any functions $f$ and $g$ which are not point-wise equal almost everywhere (see Definition~\ref{exp}): there exists $R\in \R$ s.t. $\sd(f(R),g(R))$ is ``noticeable'', where $\sd$ is the statistical distance between distributions.\footnote{Like in \cite{DOPS04} and unlike \cite{MP90}, our distinguishers between $f(R)$ and $g(R)$ will be very efficient, but we will not require this in order not to clutter the notation.} We then show that separability generically implies expressiveness, with nearly identical parameters (see Theorem~\ref{theorem1}). This is where we differ and quantitatively improve the argument from~\cite{DOPS04}: while \cite{DOPS04} used a bit-by-bit hybrid argument to show expressiveness  (for the SV source), our proof of Theorem~\ref{theorem1} used a more clever ``universal hashing trick''.\footnote{Similar trick with randomness extractors was used, in a slightly different context, by~\cite{ACMPS14}.} This allowed us to obtain results which are independent of the ranges of $f$ and $g$ (which, in turn, will later correspond to bit sizes of ciphertexts, commitments, secret shares, etc.) As a consequence, we get simple and elegant expressiveness  statements for a variety of natural sources (Corollary~\ref{spee}).

We then use a technique very similar to \cite{DOPS04} to show that most traditional privacy tasks are impossible with any ``mildly expressive'' source $\R$ (Theorem~\ref{expp} and first part of Result (2)).
Applying this to specific separable/expressive source (weak, block, SV, BCL), we immediately derive a variety of impossibility results for traditional privacy (Table~\ref{table1} and Result (3)). Although these results were derived mainly as a ``warm-up'' to our (completely new) impossibility results for differentially privacy, they offer quantitative improvements to the results of \cite{DOPS04} (due to stronger expressiveness  bounds), and also allow immediate applications to other imperfect sources. For instance, we get the following new result for BCL sources: even constant security $1/2$ for traditional privacy is impossible to achieve when the number of interventions $b = \Omega(1/\gamma)$. More importantly, instead of focusing the entire proof on some specific weak/block/SV sources~\cite{MP90,DOPS04}, our privacy impossibility results for such sources were obtained in a more modular manner, making these proofs somewhat more illuminating.

More interestingly, despite the positive result of \cite{DLMV12} regarding the SV sources, we show that expressiveness  is again sufficient to rule out even {\em differential} privacy (Theorem~\ref{imdp} and second part of Result (2)). The slight catch is that the expressiveness  requirement on $\R$ for ruling out differential privacy will be slightly higher than for traditional privacy (Theorem~\ref{imdp} vs.
Theorem~\ref{expp}). As a result, the impossibility results will (barely) miss the SV sources. However, once we consider general weak sources, or even much more structured BCL sources with $b>0$, the impossibility results come back extremely quickly! For example, when studying $\eps$-DP with utility $\rho$, $n$-bit weak sources of min-entropy $k$ are ruled out the moment $k = n- \log(\eps \rho) -O(1)$ (Theorem~\ref{weak-imp,block-imp,bcl-imp}(a)),\footnote{More generally, even $n$-bit block sources with block length $m$ and fresh min-entropy $k$ per block are ruled out when $k = m- \log(\eps \rho) -O(1)$, irrespective of the number of blocks $n/m$. See Theorem~\ref{weak-imp,block-imp,bcl-imp}(b).} while BCL sources are ruled out the moment $b = \Omega(\log(\eps \rho)/\gamma)$ (Theorem~\ref{weak-imp,block-imp,bcl-imp}(c)). As $\eps \rho$ is typically desired to be a constant, $\log(\eps \rho)$ is an even smaller constant, which means we even rule out {\em constant} entropy deficiency  $(n-k)$ or number of interventions $b$, respectively.  We also compare impossibility results for traditional and differential privacy in Table~\ref{table2}, and observe that the latter
%impossibility results
are only marginally weaker than the former. This gives us our Result (4), and the conclusion that differential privacy is still rather demanding to achieve with realistic imperfect sources of randomness.

Finally, we show that any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction (Result (5), formalized in Theorem~\ref{implies-ext}): (a) when produced, the extracted bit is
guaranteed to be almost unbiased, (b) although the extractor is
allowed to fail, it will typically succeed at least on the uniform
distribution. This result is similar in spirit, but incomparable to the result
of Bosley and Dodis~\cite{BD07}. Namely, \cite{BD07} showed that several traditional privacy primitives, including (only multi-bit) encryption and commitment (but not secret sharing) imply the existence of multi-bit deterministic extraction schemes capable of extracting almost the same number of bits as the plaintext. On the positive, our result applies to a much wider set of primitives $P$ (e.g., secret-sharing, as well as even {\em single-bit} encryption and commitment). On the negative, we can only argue a rather weak kind of single-bit extraction, where the extractor is allowed to fail, while  \cite{BD07} showed traditional, and possibly multi-bit, extraction.
}


\ignore{
In this paper, abstracting the essence of the main result in \cite{DOPS04},  we  introduce two concepts ``separability"  and ``expressiveness ".

The  motivating scenario of differential privacy is a statistical database.  A statistic is a quantity
computed from a sample. Suppose the
database is a representative sample of an underlying population, the purpose of
a privacy-preserving statistical database is to enable the user to learn  statistical facts about the underlying population.
The problem is how to release statistical information without
compromising the privacy of the individual users whose data is in the database.
Differential privacy ensures the removal or addition of a single database item does not
(substantially) affect the outcome of any analysis \cite{DMNS06}.


ORGANIZATION. The rest of the paper is organized as follows. In the following
section, we recall some concepts and notations to be used in the paper. In
Sect. 3, we introduce the concepts of
separability and expressiveness , and study their relationship.  We also enumerate several  natural imperfect sources to show their implications.
In Sect. 4, we  present the impossibility of privacy under the assumption that  the source is expressive.  In Sect. 5, we propose the  impossibility of differential  privacy under the  assumption that  the source is expressive, and analyze why this result can't be applied to   the SV source.  Set. 6 shows
the comparison about the  impossibility results of privacy and  differential privacy.
}

Due to space limitations, most proofs are deferred to the full version~\cite{DY14}.

\section{Preliminaries }


Let $U_S$ be the uniform distribution over a set $S$. For simplicity, $ U_n \overset{def}{=} U_{ \{0, 1\}^n  }$.  For a distribution or random variable $R$, let $\mathbf{r} \leftarrow R$ denote
the operation of sampling a random   $\mathbf{r}$  according to $R$ , and   $\mathbf{H}_\infty( R) \overset{def}{=}   \min_{\mathbf{r} \in \supp(R) }\log  \frac{1}{\Pr[R= \mathbf{r}]}$ denote the min-entropy of $R$.
 We call a family of distributions over $\{0, 1\}^n$ a source, denoted as $ \mathcal{R}_n$.
 All logarithms are to the base 2.




 For two random variables $R$ and $R'$  over $ \{0, 1\}^n$,  the statistical distance  between  $R$ and $R'$  is defined as
% \begin{eqnarray*}
$ \textsf{SD}(R, R' ) \overset{def}{ =} \frac{1}{2}  \sum \limits_{\mathbf{r} \in \{0, 1\}^n   } | \Pr[R= \mathbf{r} ] - \Pr[R'= \mathbf{r}]  |$. One can observe that $ \textsf{SD}(R, R' ) = \max \limits_{\textsf{Eve}} | \Pr[\textsf{Eve}(R) = 1]- \Pr[\textsf{Eve}(R' ) = 1]|$,
  where $\textsf{Eve}$ is a distinguisher.
  We say that the relative distance between $R$ and $R'$  is $ \varepsilon$, denoted as $ \textsf{RD}(R, R') =  \varepsilon$,  if  $ \varepsilon$ is the smallest number such that  $ e^{-\varepsilon } \cdot \Pr[R'= \mathbf{r} ] \leq   \Pr[R = \mathbf{r} ]  \leq   e^{\varepsilon } \cdot \Pr[R' = \mathbf{r} ]$  for all $\mathbf{r} \in \{0, 1\}^n$.  It's easy to see that $\textsf{RD}(R, R') \leq \varepsilon$ implies $ \textsf{SD}(R, R') \leq e^{\varepsilon } -1$.









% For simplicity,  in the remainder of the paper, we only consider the source  $\mathcal{R}$  such that every distribution $R \in  \mathcal{R}$ is over $\{0, 1\}^n$.


\section{Expressiveness  and its Implications to Privacy}

In this section, we introduce the concept of expressiveness  of a source.  Then  we study its  implications  to both traditional and differential privacy.

Informally, an expressive source $\mathcal{R}_n$ can separate two distributions $f(R)$ and $g(R)$, unless the functions $f$ and $g$ are  point-wise equal almost everywhere.

\begin{definition}
\label{exp}
{\slshape   We say that a source $\mathcal{R}_n$   is $(t, \delta)-$expressive if for any functions
$f, g: \{ 0, 1\}^n \rightarrow \mathcal{C}$, where   $\mathcal{C}$  is any universe,  such that $ \Pr \limits_{   \mathbf{r} \leftarrow U_n}   [ f( \mathbf{r} ) \neq g ( \mathbf{r} )   ]  \geq \frac{1}{2^t}$ for some $t \geq 0$, there exists a distribution $R \in \mathcal{R}_n$  such that
$  \textsf{SD}(f(R), g(R)  ) \geq \delta$.     }

\end{definition}



\subsection{Implications to Traditional Privacy}



We recall (or define) some  cryptographic primitives related to traditional privacy: bit extractor,    bit encryption scheme, weak bit commitment, and  bit $T$-secret sharing as follows.

\begin{definition}
\label{ext-def}
  {\slshape   We say that  $\textsf{Ext}: \{0, 1\}^n \rightarrow  \{0, 1\}$ is $(\mathcal{R}_n,  \delta)$-secure bit extractor  if for every distribution $R \in \mathcal{R}_n$,
  $|\Pr  \limits_{ \mathbf{r} \leftarrow R}  [\textsf{Ext}(\mathbf{r})=1] - \Pr \limits_{ \mathbf{r} \leftarrow R}  [\textsf{Ext}(\mathbf{r})=0]| < \delta$ (equivalently,
  $\textsf{SD}(\textsf{Ext}(R), U_1) < \delta/2$).
  %where, for a distribution $B$,  $\textsf{Bias}(B) \overset{def}{=} |2 \Pr[B=0] -1 |$.
}
\end{definition}

In the following, we consider the simplest  encryption scheme, where the plaintext is composed of a single bit $x$.

\begin{definition}
{\slshape     A $(\mathcal{R}_n, \delta )-$secure bit encryption scheme is a tuple of functions
$\textsf{Enc}: \{0, 1\}^n \times  \{0, 1\}  \rightarrow \{0, 1\}^\lambda$ and $\textsf{Dec}:  \{0, 1\}^n  \times   \{0, 1\}^\lambda \rightarrow \{0, 1\}$, where, for convenience, $ \textsf{Enc}( \mathbf{r}, x)$ (resp. $\textsf{Dec}(\mathbf{r},  \mathbf{c})$) is denoted  as $ \textsf{Enc}_{\mathbf{r}}( x )$ (resp. $\textsf{Dec}_{\mathbf{r}}(\mathbf{c})$),  satisfying the following two properties:
\vspace{-2mm}
\begin{itemize}
\item[(a)] Correctness: for all $\mathbf{r} \in \{0, 1\}^n$ and $x \in \{0, 1\}$,  $\textsf{Dec}_{\mathbf{r}}( \textsf{Enc}_{\mathbf{r}}(  x )    )= x $;
\item[(b)] Statistical Hiding:  $\textsf{SD}( \textsf{Enc}_R(0), \textsf{Enc}_R(1)) < \delta$,  for every distribution $R \in \mathcal{R}_n$.
\end{itemize}
 }
\end{definition}

\vspace{1em}


Commitment schemes allow the sender Alice to commit  a chosen value (or statement)  while keeping it secret from the receiver Bob, with the ability to reveal the committed value in a later stage.   Binding  and hiding properties  are essential to any commitment scheme.  Informally, ``binding'' means that  it's ``hard'' for Alice to alter her commitment after she has made it; ``hiding'' means that it's ``hard''  for Bob to find out the committed value without Alice revealing it.

 Each of them can be computational or information theoretical. However, we can't  achieve information theoretically  binding and information theoretically  hiding properties at the same time.  Instead of defining computational notions, we relax  binding to some very weak property,  so that
hiding and this new (very weak) binding properties both can be information theoretical. Since we aim to show an impossibility result, such relaxation  is justified.

\begin{definition}
{\slshape     A $(\mathcal{R}_n, \delta )-$secure weak  bit commitment is a function $\textsf{Com}: \{0, 1\}^n \times  \{0, 1\}  \rightarrow \{0, 1\}^\lambda$
satisfying that:  for any distribution $R \in \mathcal{R}_n$,
\vspace{-1mm}
\begin{itemize}
\item[(a)] Weak Binding:
  $\Pr  \limits_{ \mathbf{r} \leftarrow U_n }[\textsf{Com}(0; \mathbf{r})  \neq \textsf{Com}(1;  \mathbf{r})   ] \geq \frac{1}{2}$;
\item[(b)] Statistical Hiding:  $\textsf{SD}(\textsf{Com}(0; R), \textsf{Com}(1; R)) < \delta$.
\end{itemize}
 }


\end{definition}


Note that in the traditional notion of commitment, the binding property holds if it is ``hard'' to find  $\mathbf{r}_1$ and $\mathbf{r}_2$ such that
 $\textsf{Com}(0; \mathbf{r}_1) = \textsf{Com}(1; \mathbf{r}_2)$. Here we give a much weaker binding notion. We only require that the attacker can  not win with probability $ \geq \frac{1}{2}$ by choosing $\mathbf{r}_1= \mathbf{r}_2$ uniformly at random.
   For example,  $\textsf{Com}(x; r) = x \oplus r $, where $x, r \in \{0, 1\}$ can be easily verified to be a weak bit commitment for any $\delta > 0$ (despite not being a standard commitment).




\vspace{1em}

In the notion of  $T$-party Secret Sharing,  two thresholds $T_1$ and $T_2$,  where $  1 \leq T_1 < T_2 \leq T$, are involved such that (a) any $T_1$ parties have ``no information'' about the secret, (b) any $T_2$ parties enable to recover the secret.  Because our purpose is to show an impossibility result, we restrict to $T_1 =1$ and $T_2=T$, and only consider one bit secret $x$.





\begin{definition}
 {\slshape  A $(\mathcal{R}_n, \delta )-$secure bit  $T-$Secret Sharing scheme is a tuple $(\textsf{Share}_1, \\\textsf{Share}_2, \ldots, \textsf{Share}_T,  \textsf{Rec}   )$    satisfying the following two properties:
\vspace{-1mm}
\begin{itemize}
\item[(a)] Correctness:
  $\textsf{Rec}( \textsf{Share}_1(x, \mathbf{r} ), \ldots, \textsf{Share}_T(x, \mathbf{r})) = x$ for all $\mathbf{r} \in \{0, 1\}^n$ and each $x \in \{0, 1\}$;
\item[(b)] Statistical Hiding: $ \textsf{SD} ( \textsf{Share}_j(0; R), \textsf{Share}_j(1; R)) < \delta$, for every index $j \in [T]$ and  any distribution $R \in \mathcal{R}_n$.
\end{itemize}
  }

\end{definition}


\vspace{1em}

Now we abstract and generalize the  results of \cite{MP90,DOPS04} to show that expressiveness  implies the impossibility of security involving traditional privacy. See \cite{DY14} for the proof.


\begin{theorem}  \label{expp}
~\\
\vspace{-6mm}
\begin{itemize}
{\slshape \item[(a)]  When $\mathcal{R}_n$ is $(0, \delta)-$expressive,   no   $(\mathcal{R}_n, \delta)$-secure bit extractor  exists.
\item[(b)] When  $\mathcal{R}_n$ is $(0, \delta)-$expressive,
  no   $(\mathcal{R}_n, \delta)$-secure bit encryption scheme exists.
\item[(c)] When $\mathcal{R}_n$ is $(1, \delta)-$expressive,  no   $(\mathcal{R}_n, \delta)$-secure weak bit commitment  exists.
\item[(d)] When $\mathcal{R}_n$ is $(\log T, \delta)-$expressive, no $(\mathcal{R}_n, \delta)$-secure bit $T$-secret sharing  exists.
  }
\end{itemize}


\end{theorem}



\subsection{Implications to Differential Privacy  }

Dodis et al. \cite{DLMV12} have shown how to do differential privacy with respect to  the $\gamma$-SV source for all ``queries of low  sensitivity''. Since
we aim to show impossibility results, henceforth we only consider the simplest case: let $ \mathcal{D} = \{0, 1\}^N$ be  the space of all databases and for $D \in \mathcal{D}$,  the query function $q$ is the Hamming weight function  $wt(D) = |\{ i \mid D(i) =1 \} |$, where $D(i)$ means the $i$-th bit (``record'') of  $D$.
If the source $\mathcal{R}_n$ has only one distribution $ U_n$, $\mathcal{R}_n$ is denoted by $U_n$ for simplicity.   For any $D, D' \in \mathcal{D}$,  the discrete distance function between them   is defined by  $ \Delta( D, D' ) \overset{def}{=} wt(D \oplus D')$, where $ \oplus$ is the bitwise exclusive OR operator.   We say that  $D$ and  $D'$ are neighboring if   $\Delta( D, D' ) =1$.
 A mechanism $M$ is
an algorithm that takes as input a database $D  \in \mathcal{D}$ and a distribution $R \in \mathcal{R}_n$, and outputs a  random value $z$.
Informally, we wish $z = M(D, R)$ to approximate the true value $wt(D)$ without revealing
too much information about any individual $D(i)$. More formally, a mechanism is differentially private for the Hamming weight queries if replacing an entry in the database with one containing fake information only
changes the output distribution of the mechanism by a small amount.  In other words, evaluating the
mechanism  on two neighboring databases, does not change the outcome
distribution by much. On the other hand, we define its utility to be the expected difference between
the true answer $wt(D)$ and the output of the mechanism. More formally,


\begin{definition}
\label{dp}
 {\slshape  Let $ \varepsilon \geq 0$ and $ \mathcal{R}_n$ be a source.  A mechanism $M$ (for the Hamming weight queries) is $(\mathcal{R}_n, \varepsilon)$-differentially private
 if for all neighboring databases  $D_1, D_2 \in \mathcal{D}$, and  all  distributions $R \in   \mathcal{R}_n$, we have $\rd(M(D_1,R), M(D_2,R))\le \varepsilon$.
%
 Equivalently, for any possible output $z$:
 %, and  any  distribution $R \in   \mathcal{R}_n$:
  $$ \frac{\Pr \limits_{\mathbf{r} \leftarrow R }[M(D_1,  \mathbf{r})=z  ]}{ \Pr \limits_{\mathbf{r} \leftarrow R}[M(D_2, \mathbf{r})=z ]}  \leq e^{\varepsilon}.$$
%  1+ \varepsilon.$$

}

\end{definition}

Note that for $\varepsilon<1$, we can rather accurately approximate $e^\varepsilon$ by $1+\varepsilon$.
%Note that in most literature,  differential privacy has been defined by limiting the upper bound of  the %ratio of probabilities to
%$ e^\varepsilon$. Here we employ the bound $1+ \varepsilon$ which is the same as that of \cite{DLMV12}.
%This is justified as we always have $ 1+ \varepsilon \leq e^\varepsilon$ and when $ \varepsilon \ll 1$, $ %e^\varepsilon \approx 1+ \varepsilon$.



\vspace{0.15cm}


\begin{definition}
\label{uti}
{\slshape  Let $ 0 < \rho  \leq N/4$ and $ \mathcal{R}_n$ be a source. A mechanism $M$ has $( \mathcal{R}_n, \rho)$-utility  for the Hamming weight queries, if  for all databases $D \in   \mathcal{D}$  and all distributions  $ R \in \mathcal{R}_n$, we have
$ \mathbb{E}_{ \mathbf{r} \leftarrow  R} [ |M(D,  \mathbf{r}) -  wt(D)| ] \leq \rho.$

}
\end{definition}


%\begin{definition}
%\label{ap}
% {\slshape   We say the Hamming weight queries admit  accurate
%and private mechanisms w.r.t. $ \mathcal{R}_n$  if there exists a function $g(\cdot)$  such that for all $ %\varepsilon > 0$ there exists
%a mechanism  $M_{\varepsilon}$  that is $( \mathcal{R}_n, \varepsilon )$-differentially private and has $( %\mathcal{R}_n, g( \varepsilon) )$-utility. $ \mathcal{M} =  \{ M_{\varepsilon}\}$ is called  a class of %accurate and private mechanisms for the Hamming weight queries   w.r.t.  $\mathcal{R}_n$.
%}


%\end{definition}




\vspace{0.15cm}

We show that, much like with traditional privacy, expressiveness  implies  impossibility of differential privacy with imperfect randomness, albeit with slightly more demanding parameters.

\begin{theorem}
\label{imdp}
{\slshape
Assume $1/(8 \rho) \le \varepsilon \le 1/4$ and the source $ \mathcal{R}_n$
 is $( \log( \frac{ \rho \varepsilon  }{\delta} ) +4, \delta )-$\\expressive, for some  $ 2\varepsilon \le \delta \le 1$. Then no
 $(\mathcal{R}_n, \varepsilon )-$differentially private and $( U_n, \rho)$-accurate mechanism  for the Hamming weight queries exists.} In particular, plugging $\delta= 2 \varepsilon$ and $\delta= \frac{1}{2}$, respectively, this holds if either \\
 \vspace{0.3cm}
(a) $\mathcal{R}_n$ is $(  3 + \log(\rho), 2\varepsilon)-$expressive; or (b)  $ \mathcal{R}_n$ is $(5+ \log( \rho \varepsilon), \frac{1}{2} )-$expressive.



\end{theorem}

\ignore{
The proof can be found in Appendix~\ref{app:imdp}, but we give the high-level idea.

}



The high-level idea is as follows. For two databases $D$ and $D'$, define two functions $f(  \mathbf{r}) \overset{def}{=} M(D,   \mathbf{r} )$ and $ g(\mathbf{r}) \overset{def}{=} M(D',  \mathbf{r})$.   Intuitively, for all $R\in \mathcal{R}_n$, since $\textsf{RD}(f(R),   g(R)) \leq \varepsilon \cdot \Delta (D, D')$ implies $ \textsf{SD}(f(R),   g(R)   ) \leq e^{\varepsilon \cdot \Delta (D, D')} -1$, we could use expressiveness  to argue that $f(  \mathbf{r})
= g(  \mathbf{r})$ almost everywhere, which must eventually contradict utility (even for uniform distribution). However, we can't use this technique directly, because if $\varepsilon \cdot \Delta (D, D')$  is large enough, then $ e^{\varepsilon \cdot \Delta (D, D')} -1  > 1$, which is greater than the general upper bound $1$ of the statistical distance. Instead, we simply use this trick on close-enough databases $D$ and $D'$, and then use a few ``jumps'' from $D_0$ to $D_1$, etc., until eventually we must violate the $\rho$-utility.



\begin{proof}  Assume for contradiction that there exists
such a mechanism $M$.   Let $\mathcal{D}' \overset{def}{=} \{D \mid wt(D) \leq 4 \rho\}$.  Denote

\begin{equation}
  \textsf{Trunc} (x) \overset{def}{=}   \left\{
\begin{aligned}
0, & ~~ if ~ x < 0; \nonumber\\
x, & ~~ if ~  x \in \{0, 1, \ldots, 4 \rho\}; \nonumber\\
4\rho, & ~~ otherwise.
\end{aligned}
\right.
\end{equation}

 For any $D \in \mathcal{D}'$, define the truncated mechanism $ M' \overset{def}{=}  \textsf{Trunc} (M)$ by $ M'(D, \mathbf{r}) \overset{def}{=} \textsf{Trunc} (  M(D, \mathbf{r}))$.  Since for every $D \in \mathcal{D}'$, we have $wt(D) \in   \{0, 1, \ldots, \\4 \rho\}$,
 $M'$ still has $(U_n, \rho)-$utility on $\mathcal{D}'$. Additionally, from Definition \ref{dp}, it's straightforward that $M'$ is  ($\mathcal{R}_n, \varepsilon$)-differentially private on $\mathcal{D}'$. In the following, we only consider the truncated mechanism $ M' $ on $\mathcal{D}'$.

Let $t =  \log( \frac{ \rho \varepsilon  }{\delta} ) +4$ and $s = \frac{\delta}{2\varepsilon}$. Notice, $1\le s \le 1/(2\varepsilon) \le 4\rho$, $e^{\varepsilon s} - 1 < \delta$, and $2^t = 8\rho/s$.

We start with the following claim:
 \begin{claim}
   {\slshape   Consider any databases   $D, D' \in  \mathcal{D}'$, s.t. $ \Delta(D, D') \le s$,
%   , and any fixed distribution $R \in \mathcal{R}_n$.
and denote $ f(\mathbf{r}) \overset{def}{=} M'(D,  \mathbf{r}  )$ and $ g(\mathbf{r}) \overset{def}{=} M'(D',  \mathbf{r})$.  Then $\Pr \limits_{ \mathbf{r} \leftarrow U_n }[ f(  \mathbf{r}) \neq g(  \mathbf{r}) ] < \frac{1}{ 2^t}$.}
 \end{claim}

 \begin{proof}
Since $M'$ is    $( \mathcal{R}_n,     \varepsilon)$-differentially private, then for all
$R\in \mathcal{R}_n$, we have $ \textsf{RD}( f(R), g(R) ) \leq \varepsilon \cdot  \Delta (D, D')  \leq \varepsilon \cdot  s$. Hence, $\textsf{SD}(f(R), g(R)) \leq e^{\varepsilon \cdot  s} - 1 < \delta$, by our choice of $s$.  Since this holds for all $R\in \mathcal{R}_n$ and  $ \mathcal{R}_n$  is
$(t, \delta)-$expressive, we conclude that it must be the case that $\Pr \limits_{ \mathbf{r} \leftarrow U_n }[ f(  \mathbf{r}) \neq g(  \mathbf{r}) ] < \frac{1}{ 2^t}$.

%\rightline { $\Box$ }
\end{proof}

Coming back to the main proof, consider  a sequence of databases $D_0, D_1, \cdots, \\D_{4\rho/s}$ such that
$wt( D_i) =  i\cdot s$ and $\Delta (D_i, D_{i+1}) =  s$.  Denote $f_i(R) \overset{def}{=} M'(D_i,  R  )$ for all $i \in \{0, 1, \ldots, 4\rho/s\}$.
From the above Claim, we get that $ \Pr \limits_{ \mathbf{r} \leftarrow U_n}   [  f_i (\mathbf{r} ) \neq  f_{i+1} (\mathbf{r} ) ]   <  \frac{1}{ 2^t  }$. By the union bound and our choice of $s$ and $t$,
\begin{equation}\label{temp}
\Pr \limits_{ \mathbf{r} \leftarrow U_n}   [  f_0 (\mathbf{r} ) \neq  f_{ 4\rho/s } (\mathbf{r} ) ] <  \frac{4\rho}{2^t \cdot s}\le \frac{1}{2}
\end{equation}

\noindent
Let $\alpha \overset{def}{=}   \mathbb{E}_{ \mathbf{r} \leftarrow  U_n} [~f_{4\rho/s } (\mathbf{r}  ) - f_0 (\mathbf{r})~]$.   From $(U_n,\rho)$-utility, we get  that
$$\alpha \geq (wt(D_{4\rho/s}) - \rho) - (wt(D_0) + \rho) = (4 \rho - \rho) - (0+\rho) =2 \rho.$$
On the other hand, from Inequation~(\ref{temp}),
$$\alpha  \leq \Pr \limits_{ \mathbf{r} \leftarrow U_n  } [f_0 (\mathbf{r})  \neq   f_{4\rho/s} (\mathbf{r}  ) ] \cdot \max_{\mathbf{r}} |f_{4\rho/s}(\mathbf{r}) - f_0(\mathbf{r})| <   \frac{1}{2}  \cdot 4 \rho = 2\rho,$$ which is a contradiction.

%\rightline { $\Box$ }
\end{proof}


%Details follow.


\section{ Separability and its Implications }



Expressiveness  is a powerful tool, but it's hard for us to use it directly. In this section, we introduce the concept of
separability and show that it implies expressiveness, and also has its own
applications to (weak) coin flipping.  Several typical  examples can been seen in Section 5.


Intuitively,  separable sources $\mathcal{R}_n$ allow one to choose a distribution $R\in \mathcal{R}_n$
capable of ``separating'' any sufficiently large, disjoint sets $G$ and $B$:  increasing a relative weight of one set w.r.t. $R$ without doing the same for the counterpart of the other one.

\begin{definition}
\label{sep}
 {\slshape   We say that a source $\mathcal{R}_n$  is $ (t, \delta)-$separable if  for all
$G, B \subseteq \{0, 1\}^n$,  where $G \cap B = \emptyset$ and  $|G \cup B| \ge 2^{n-t}$,   there exists a distribution $R \in  \mathcal{R}_n$ such that
$| \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in G] - \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in B]~| \geq  \delta.$



%OLD. new t essentially becomes old t+1
% {\slshape   We say that a source $\mathcal{R}_n$  is $ (t, \delta )-$separable if   for all
%$G, B \subseteq \{0, 1\}^n$,  where $G \cap B = \emptyset$,  $| G| \geq \max ( |B|,  2^{n-t}  )$, and $t %\geq 0$,   there exists a distribution $R \in  \mathcal{R}_n$ such that  $$\Pr \limits_{ \mathbf{r} %\leftarrow R }[\mathbf{r} \in G] - \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in B] \geq  %\delta.$$

     }

\end{definition}

% \noindent\textbf{Example 1.}\   $ \mathcal{W}eak_n (n-1)$ is $(t, \frac{1}{2^{t-1}   } )-$separable where $t \geq 1$.


% \begin{proof} Assume that  $G, B \subseteq \{0, 1\}^n$ where $G \cap B = \emptyset$ and $| G| \geq \max ( |B|,  2^{n-t}  )$.

% $  \mathbf{Case~1}$:   First suppose that $|G| \leq 2^{n-1}$.  Choose a set $S \subset \{0, 1\}^n$ of size $|S|= 2^{n-1}$ such that $G \subseteq S$ and $ B \cap S = \emptyset$.  Then $$ \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow  U_S  }[ \mathbf{r} \in B]  = \frac{ 1}{2^{n-1}} \cdot |G|  -0 \geq  \frac{1}{2^{t-1}}. $$



% $  \mathbf{Case~2}$:  Now assume that $|G| > 2^{n-1}$.  Then pick any $S \subset \{0, 1\}^n$ of size   $|S|= 2^{n-1}$ such that $S \subset G$. Then
%$$ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]= \frac{1+ \gamma}{2^n} \cdot |S| + \frac{1- \gamma}{2^n} \cdot |G \setminus  S| - \frac{1- \gamma}{2^n} \cdot |B|  $$
% $$ \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in B]  = 1- 0 =1.  $$
% From \cite{3}, we get that there exists a  distribution $R  \in  \mathcal{SV}(\gamma, n)$  such that  $ \frac{\Pr \limits_{ \mathbf{r} \leftarrow R }[ \mathbf{r} \in G ]}{  \Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in B ]  }  \geq (1 + \gamma) \cdot \frac{|G|}{|B|} \geq  (1 + \gamma) \cdot \frac{  2^{n-t}}{2^n}$






 %Let $S$ be the subset of $  \{0, 1\}^n$  such that $|S|=2^{n-1}$. Let $R= U_S$. Then  $ \Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in G  ] \geq \frac{2^{n-t}}{2^{n-1}}$.  Therefore,   $ \frac{\Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in G  ] }{\Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in B  ]} \geq \frac{\frac{N}{2^{n-1}}  }{1}= \frac{N}{2^{n-1}}$.

% \end{proof}


\subsection{Separability Implies Expressiveness }

We investigate the relationship between separability and expressiveness.
We show that separable sources must be expressive. The high-level idea of the proof comes from the work of \cite{DOPS04} (who only applied it to SV sources), but we  quantitatively improve the technique of~\cite{DOPS04},
 \ignore{
 {\color{red} (Could the previous sentence be changed into ``We abstract the work of  \cite{DOPS04} (who only applied it to SV sources), but we quantitatively improve the parameters of \cite{DOPS04},''?) }  }
 by making the gap between expressiveness  and separability independent of the range $\mathcal{C}$ of the functions $f$ and $g$. See  \cite{DY14}  for the proof.
%In other words, an expressive source $  \mathcal{R}_n$ allows one to choose a distribution $ R \in \mathcal{R}_n$ such that it can   express  the statistical   distinguishability  of  two distributions  $f(R)$ and $g(R)$ if  the functions $f$ and $g$  are not  equal on at least $ 2^{n-t}$  points.



\begin{theorem}
\label{theorem1}
{\slshape  If a source $\mathcal{R}_n$  is $( t+1,  \delta)-$separable,  then it's
$(t, \delta )$-expressive.    }
\end{theorem}

 \begin{remark}  \label{efficient}
 Note that if the universe $ \mathcal{C}  $ is a subset of $  \{0, 1\}^{ poly (n)}$, then the universal hash function family in the proof of Theorem \ref{theorem1} can be made efficient (in $n$). Hence, the distinguisher  $ \textsf{Eve}$ can be made efficient as well. Therefore, there exists an efficient  distinguisher $\textsf{Eve}$ such that $|\Pr \limits_{\mathbf{r} \leftarrow R }[\textsf{Eve} (f(\mathbf{r})) =1] - \Pr \limits_{\mathbf{r} \leftarrow R }[\textsf{Eve} (g(\mathbf{r})) =1] | \geq \delta$. Namely,  $ f(R)$ is ``$\delta$-{\slshape computationally distinguishable}'' from $g(R)$.
\end{remark}


Combining Theorem \ref{theorem1} with Theorems  \ref{expp} and \ref{imdp}, we get


\begin{corollary}  \label{sep-privacy}
 {\slshape
 ~\\
\vspace{-6mm}
\begin{itemize}
\item[(a)]  If $\mathcal{R}_n$ is $(1, \delta)-$separable, then  no   $(\mathcal{R}_n, \delta)$-secure bit extractor  exists.
\item[(b)] If  $\mathcal{R}_n$ is $(1, \delta)-$separable,  then
  no   $(\mathcal{R}_n, \delta)$-secure bit encryption  exists.
\item[(c)] If  $\mathcal{R}_n$ is $(2, \delta)-$separable, then  no   $(\mathcal{R}_n, \delta)$-secure weak bit commitment  exists.
\item[(d)] If  $\mathcal{R}_n$ is $(\log T +1, \delta)-$separable, then  no   $(\mathcal{R}_n, \delta)$-secure bit $T$-secret sharing  exists.
\item[(e)] Assume $1/ (8 \rho) \le \varepsilon \le 1/4$ and  $ \mathcal{R}_n$ is $( \log( \frac{ \rho \varepsilon  }{\delta} ) +5, \delta )-$separable, for some  $ 2\varepsilon \le \delta \le 1$. Then no $(\mathcal{R}_n, \varepsilon )-$differentially private and $( U_n, \rho)$-accurate mechanism  for the Hamming weight queries exists.  In particular, plugging $\delta= 2 \varepsilon$ and $\delta= \frac{1}{2}$, respectively, this holds if either (e.1) $ \mathcal{R}_n$ is $(4 + \log(\rho), 2\varepsilon)-$separable; or  (e.2) $ \mathcal{R}_n$ is $(6 + \log( \rho \varepsilon), \frac{1}{2})-$separable.
\end{itemize}
}

\end{corollary}

The above results are  illustrated by several typical sources in Section 5.

\subsection{Separability and Weak Bit Extraction}\label{sec:weak-extr}

In this section, we define weak bit extraction and
show that weak bit extraction is equivalent to NON-separability. Then we propose its implications to privacy.


\ignore{
 {\color{red} New:  Separability  is also useful by itself.   In this section, we define weak bit extractor and
show its the equivalence to NON-separability.  Then we propose its implications to privacy.  }
}


Recall, Bosley and Dodis~\cite{BD07} initiated the study of the general question: {\em does privacy inherently require ``extractable'' source of randomness}? A bit more formally, if a primitive $P$ admits $(\mathcal{R}_n, \delta)$-secure implementation, does it mean  one can construct a (deterministic, single- or multi-) bit extractor from $\mathcal{R}_n$?

They also obtained very strong affirmative answers to this question for several traditional privacy primitives, including (only multi-bit) encryption and commitment (but not secret sharing, for example). Here we make the observation that our impossibility results give an incomparable (to~\cite{BD07}) set of affirmative answers to this question. On the positive, our results apply to a much wider set of primitives $P$ (e.g., secret-sharing, as well as even single-bit encryption and commitment). On the negative, we can only argue a rather weak kind of single-bit extraction (as opposed to \cite{BD07}, who showed traditional, and possibly multi-bit extraction). Our weak notion of extraction is defined below.

\begin{definition}
  {\slshape   We say that $\textsf{Ext}: \{0, 1\}^n \rightarrow  \{0, 1,\bot\}$ is $(\mathcal{R}_n,  \delta,\tau)$-secure weak bit extractor if
\vspace{-2mm}
  \begin{itemize}
  \item[(a)] for every distribution $R \in \mathcal{R}_n$,
  $|\Pr \limits_{\mathbf{r} \leftarrow R } [\textsf{Ext}(\mathbf{r})=1] - \Pr\limits_{\mathbf{r} \leftarrow R }[\textsf{Ext}(\mathbf{r})=0]|< \delta$;
   \item[(b)] $\Pr \limits_{\mathbf{r} \leftarrow U_n }  [\textsf{Ext}(\mathbf{r})\neq \bot]\ge \tau$.
\end{itemize}
}
\end{definition}

We briefly discuss this notion, before showing our results. First, we notice that setting $\tau=1$ recovers the notion of traditional bit-extractor given in Definition~\ref{ext-def}. And, even for general $\tau<1$, % Like traditional bit-extractor in Definition~\ref{ext-def},
the odds of outputting $0$ or $1$ are roughly the same, for any distribution $R$ in the source. However, now the extractor is also allowed to output a failure symbol $\bot$, which means that each of the above two probabilities can occur with probabilities noticeably smaller than $1/2$. Hence, to make it interesting, we also add the requirement that $\textsf{Ext}$ does not output $\bot$ all the time. This is governed by the second parameter $\tau$ requiring that $\Pr \limits_{\mathbf{r} \leftarrow R }[\textsf{Ext}(\mathbf{r})\neq \bot]\ge \tau$. Ideally, we would like this to be true for any distribution $R$ in the source. Unfortunately,
%we will see shortly that
such a desirable guarantee will not be achievable in our setting (see Remark~\ref{DS}). Thus, to salvage a meaningful and realizable notion, we will only require that  this non-triviality guarantee at least holds for $R\equiv U_n$. Namely, while we do not rule out the possibility that some particular distributions $R$ might force $\textsf{Ext}$ to fail the extraction with high probability,
we still ensure that: (a) when the extraction succeeds, the extracted bit is unbiased for {\em any} $R$ in the source; (b) the extraction succeeds with noticeable probability at least when $R$ is (``close to'') the uniform  distribution $U_n$.

We now observe (and prove in \cite{DY14})
 that the notion of weak bit-extraction is simply a different way to express (the negation of) our notion of separability!

\begin{lemma}
\label{weakext}
 {\slshape
  $\mathcal{R}_n$ has a
  $(\mathcal{R}_n,  \delta, 2^{-t})$-secure weak bit extractor if and only if   $\mathcal{R}_n$
 is \underline{not} $(t, \delta)$-separable.
    }
\end{lemma}

%
Combining Lemma~\ref{weakext} with  the counter-positive of Corollary \ref{sep-privacy}, we get

\begin{theorem}  \label{implies-ext}
{\slshape
~\\
\vspace{-6mm}
\begin{itemize}
\item[(a)]  If $(\mathcal{R}_n, \delta)$-secure bit encryption scheme exists, then $(\mathcal{R}_n, \delta, \frac{1}{2})$-secure weak bit-extraction exists.
\item[(b)]  If $(\mathcal{R}_n, \delta)$-secure weak bit commitment exists, then $(\mathcal{R}_n, \delta, \frac{1}{4})$-secure weak bit extraction exists.
\item[(c)]  If $(\mathcal{R}_n, \delta)$-secure bit $T$-secret-sharing exists, then $(\mathcal{R}_n, \delta, \frac{1}{2T})$-secure weak bit extraction exists.
\item[(d)]  If  $(\mathcal{R}_n, \varepsilon)-$differentially private and $( U_n, \rho )$-accurate mechanism  for the Hamming weight queries exists, then $(\mathcal{R}_n, 2\varepsilon, \frac{1}{16 \rho})$-secure weak bit extraction exists.
\end{itemize}
  }
\end{theorem}

It is also instructive to see the explicit form of our weak bit extractor. For example, in the case of bit encryption (part (a), other examples similar), we get

\begin{equation}
  \textsf{Ext} (\br) \overset{def}{=}   \left\{
\begin{aligned}
1, & ~~ \mbox{if} ~ h^*(\textsf{Enc}_{\br}(1)) = 1\mbox{~~and~~} h^*(\textsf{Enc}_{\br}(0)) = 0, \nonumber\\
0, & ~~ \mbox{if} ~ h^*(\textsf{Enc}_{\br}(1)) = 0\mbox{~~and~~} h^*(\textsf{Enc}_{\br}(0)) = 1, \nonumber\\
\bot, & ~~ \mbox{otherwise}~~ (\mbox{i.e.,~if} ~ h^*(\textsf{Enc}_{\br}(1)) = h^*(\textsf{Enc}_{\br}(0))),
\end{aligned}
\right.
\end{equation}
where $h^*$ is the  boolean universal hash function from the proof of Theorem~\ref{theorem1}, chosen as to ensure $\Pr \limits_{\mathbf{r}  \leftarrow U_n }[\textsf{Ext}(\mathbf{r})\neq \bot] = \Pr \limits_{\br\leftarrow U_n}[h^*(\textsf{Enc}_{\br}(0))\neq h^*(\textsf{Enc}_{\br}(1))] \ge \frac{1}{2}.$
When the bit encryption (resp. commitment, secret sharing, DP mechanism) is computationally efficient (in $n$), our bit extractor is efficient too. This means that even computationally secure analogs of encryption (commitment, secret sharing, DP mechanism) imply efficient, statistically secure weak bit extraction.

\begin{remark}
\label{DS}
As we mentioned, the major weakness of our weak bit extraction
definition comes from the fact that the non-triviality condition
$\Pr \limits_{\mathbf{r} \leftarrow R}[\textsf{Ext}(\mathbf{r})\neq \bot] \geq \tau$ is only required for $R \equiv
U_n$.
Unfortunately, we observe that the analog of
Theorem~\ref{implies-ext}.(a)-(c) is no longer true if we require the
extraction non-triviality to hold for all $R \in \mathcal{R}_n$.
Indeed, this stronger notion of $(\mathcal{R}_n,\delta, \tau)$-secure
weak bit extraction clearly implies traditional
$(\mathcal{R}_n, 1 + \delta - \tau)$-secure bit extraction (by mapping
$\bot$ to $1$). On the other hand,
Dodis and Spencer \cite{DS02}
gave an example of a source $\mathcal{R}_n$ for which, for any
$\varepsilon >0 $, there exists $(\mathcal{R}_n, \varepsilon)$-secure
bit encryption (and hence, weak commitment and $2$-secret sharing)
scheme, but no $(\mathcal{R}_n, 1-2^{1-n/2})$-secure bit-extraction.
Thus, the only analogs of Theorem~\ref{implies-ext}.(a)-(c) we could
hope to prove using the strengthened notion of weak bit extraction
would have to satisfy $\tau \le \delta + 2^{1-n/2}$, which is not a very
interesting weak bit extraction scheme (e.g., if $\delta$ is
``negligible'', then the extraction succeeds with ``negligible''
probability as well). \footnote{For differential privacy (part (d)), we
 do not have an analog of the counter-example in  \cite{DS02}, and
 anyway the value  $ \tau = O (1 / \rho) \ll \delta = O(\varepsilon)$ (so no contradiction).
 %  $\tau = O (1/ \rho) \ll \delta = O( \eps )$.
 Of course, this does not imply that a stronger bit extraction result should be true; only that it is not definitely false.}
 \end{remark}






\section{Privacy with Several Typical Imperfect Sources }



  Now we define several  imperfect sources $  \mathcal{R}_n $:  the   $(k,n)-$source \cite{CG88}, $n$-bit $(k,m)$-block source \cite{CG88},  $n$-bit $\gamma$-Santha-Vazirani (SV) source \cite{SV86},  and $(\gamma, b, n)$-Bias-Control Limited (BCL)  source \cite{D01} below.  Then we prove all these sources  are separable.   Based on this result, we show  they are all expressive.  Afterwards, we study the impossibility of  traditional and differential privacy with weak, block and BCL  sources, and explain why the SV source does not work. Finally,   we compare the impossibility of traditional and differential privacy.


 \begin{definition}
 {\slshape
     The $(k, n)$-source (or $n$-bit weak source with min-entropy at least $k$)  is defined by  $\mathcal{W}eak(k, n) \overset{def}{=} \{ R  \mid  \mathbf{H}_\infty(R) \geq k, \text{where}~R~\text{is over}~\{0, 1\}^n\}$. }
\end{definition}

Block sources are generalizations of weak sources, allowing $n/m$ blocks $R_1,\ldots,\\R_{n/m}$ each having $k$ fresh bits of entropy.\footnote{For consistency with prior work, we only assume that $R_i$ has $k$ fresh bits conditioned on the prior blocks, but our impossibility results easily extend to the case when we condition on both the past and the future blocks.\label{foot:sv}}

 \begin{definition}
 {\slshape  Let  $m$ divide $n$, and $R_1,  \ldots,  R_{n/m}$  be a sequence of Boolean random
variables  over $\{0,1\}^m$.   A probability distribution $ R =( R_1,    \ldots, R_{n/m})$  over $  \{0, 1\}^n $
is an $n$-bit $(k,m)$-block distribution, denoted by $Block(k, m, n)$,  if for all $i \in [n/m]$ and for every $s_1,\ldots,s_{i-1}\in \{0,1\}^m$, we have
$$\mathbf{H}_\infty( R_i\mid R_1\ldots R_{i-1} = s_1\ldots s_{i-1}) \geq k.$$
We define the  $n$-bit $(k,m)$-block source $\mathcal{B}lock(k,m, n)$ to be the set of  all $n$-bit $(k,m)$-block distributions.

}
\end{definition}

Hence, weak sources correspond to $m=n$ (i.e., one block). From the other extreme, SV  sources as shown in Definition \ref{defSV}  correspond to $1$-bit blocks (i.e., $m=1$). In this case, it is customary to express the imperfectness of the source as the function of its ``bias'' $\gamma$ instead of min-entropy $k$. Of course, for $1$-bit random variables bias and min-entropy are related by $2^{-k} = (1+\gamma)/2$.

 \begin{definition}
 \label{defSV}{\slshape  Let   $r_1, \ldots,  r_n$  be a sequence of Boolean random
variables and $ 0 \leq \gamma < 1$.   A probability distribution $ R =( r_1,   \ldots, r_n)$  over $  \{0, 1\}^n $
is an $n$-bit $\gamma$-Santha-Vazirani  distribution, denoted by $SV(\gamma, n)$,  if for all $i \in \{1, \ldots, n\}$ and every string $s \in  \{0, 1\}^{i-1}$,   $ \frac{1-\gamma}{2} \leq \Pr[r_i=1 \mid r_1   \ldots r_{i-1} = s] \leq \frac{1+\gamma}{2}$  holds.
We define the  $n$-bit $\gamma$-SV  source $\mathcal{SV}(\gamma, n)$ to be the set of  all $n$-bit $\gamma$-SV distributions.

}
\end{definition}



Finally, we define BCL sources~\cite{D01}.

\begin{definition}

\label{bcldef}
 {\slshape   Assume that   $ 0 \leq \gamma < 1$.  The $( \gamma, b, n)$-Bias-Control Limited (BCL) source   $\mathcal{BCL}(\gamma, b, n)$  generates
$n$ bits $r_1,  \ldots,  r_n$,  where  for all $i  \in \{1, \ldots, n\}$, the value  of $r_i$
can depend on  $r_1,  \ldots,  r_{i-1}$ in one of the following two ways:
\vspace{-2mm}
\begin{itemize}
\item[(a)]  $r_i$ is determined by $r_1,  \ldots, r_{i-1}$,  but this can  happen for at most $b$ bits.  This  rule of determining a bit is called an
  intervention.
\item[(b)]  $\frac{1-  \gamma}{2}  \leq   \Pr[r_i=1 \mid r_1  r_2 \ldots r_{i-1}]  \leq \frac{1+ \gamma}{2}$.

\end{itemize}

\noindent Every distribution over $\{0, 1\}^n$ generated from    $\mathcal{BCL}(\gamma, b, n)$  is called a  $( \gamma, b, n)$-BCL distribution  BCL$(\gamma, b, n)$.







 }


\end{definition}





In particular, if $b = 0$,   $ \mathcal{BCL}(\gamma, b, n)$   degenerates into $ \mathcal{SV}(\gamma, n)$ \cite{SV86}; if $ \gamma=0$, it yields the sequential-bit-fixing source of Lichtenstein,  Linial, and  Saks  \cite{LLS89}.




\subsection{Separability Results  }


\ignore{
In the following, we propose that the above sources  are separable. It should be noted that: (a)
The results for the weak and SV sources are implicitly known; (b) The BCL source was not considered before, but it is not hard to prove its separability  given
careful application of prior work; (c) The separability of the block source is new. It was not considered
before because the SV source is  a block source with each block of length  1, and  \cite{MP90,DOPS04}  showed
traditional privacy impossible even with the SV source (hence with the block source). But in
light of \cite{DLMV12}, where differential privacy   is possible with the SV source, we find it important
to precisely figure out the separability of the block source. Which is what we obtain
as a new result (in fact,   the improved  result about the SV source will follow as a corollary of
our new  result about the block source!)
}

In the following, we propose that the above sources  are separable. It should be noted that: (a)
The results for the weak and SV sources are implicitly known; (b) The BCL source was not considered before, but it is not hard to prove its separability  given
careful application of prior work; (c) The separability of the block source is new. It was not considered
before because the SV source is a block source with each block of length 1, and  \cite{MP90,DOPS04}  showed
traditional privacy impossible even with the SV source (hence with the block source). But in
light of \cite{DLMV12}, where differential privacy   is possible with the SV source, we find it important
to precisely figure out the separability of the block source.   A naive approach would be to employ the so called $\gamma$-biased half-space source (see \cite{DY14}), introduced by \cite{RVW04} and \cite{DOPS04}, which is both $\gamma$-SV  and  $(m- \log \frac{1+ \gamma}{1- \gamma}, m)$-block sources. We can easily conclude that (1) $\mathcal{SV}(\gamma, n)$ is $(t,   \frac{\gamma  }{2^{t+1}})-$separable, and  (2) $\mathcal{B}lock(k, m, n)$ is  $(t,   \frac{ 2^{m-k} -1  }{ 2^{t+1} \cdot (2^{m-k} +1)} )-$separable.
 \ignore{
 Please see the appendix for details. }
  However, these results  are somewhat sub-optimal.
  %It'll be much better if we can obtain $(t, \frac{1}{2})-$separability.  To achieve this goal, %
Instead,  we introduce a new separability bound for block sources in Lemma \ref{lemma3} (b), and use it to get an improved result about the SV sources as well (see \cite{DY14} for the proof).

\begin{lemma}     {\slshape
\label{lemma3}
~\\
\vspace{-6mm}
\begin{itemize}
 \item[(a)]  Assume that $k \leq n-1$. Then  $ \mathcal{W}eak(k,n)$ is   $(t, 1)-$separable when  $k \leq n -t-1$, and $(t, 2^{n-t-k-1} )-$separable when $ n -t -1 <  k  \leq n -1$.  In particular,   it's   $(t, \frac{1}{2})-$separable when $k \leq n-t$.
 \item[(b)]  $\mathcal{B}lock(k,m,n)$ is $\left(t, \frac{1}{1 + 2^{t+1}\cdot \left(\frac{2^k-1}{2^m-2^k}\right)} \right)-$separable. In particular, it is $(t, 1/(1+2^{2+t+k-m}))-$separable when $k\le m-1$ (and, hence, $(t, \frac{1}{2})-$separable when $k  \leq m -t-2$).
 \item[(c)]  $  \mathcal{SV}(\gamma, n)$ is $(t,   \frac{\gamma  }{2^{t}} )-$separable.
%  (c)  $  \mathcal{SV}(\gamma, n)$ is $(t,   \frac{\gamma  }{2^{t+1}} )-$separable.\\
 \item[(d)]  $ \mathcal{BCL}(\gamma, b, n)$ is $(t,     1-  \frac{2^{t+2} }{  (1+ \gamma)^b})-$separable.   In particular,  it is  $(t,  \frac{1}{2})-$separable  for  $ b \geq \frac{t+3}{ \log (1+ \gamma)}= \Theta(\frac{t+1}{\gamma})$.
\end{itemize}  }

\end{lemma}


\ignore{
\begin{lemma}     {\slshape
\label{lemma3}  (a)  Assume that $k \leq n-1$. Then  $ \mathcal{W}eak(k,n)$ is   $(t, 1)-$separable when  $k \leq n -t-1$, and $(t, 2^{n-t-k-1} )-$separable when $ n -t -1 <  k  \leq n -1$.  In particular,   it's   $(t, 1/2)-$separable when $k \leq n-t$.  \\
  (b)  $\mathcal{B}lock(k,m,n)$ is $\left(t, 1/(1 + 2^{t+1}\cdot \left(\frac{2^k-1}{2^m-2^k}\right)) \right)-$separable. In particular, it is $(t, 1/(1+2^{2+t+k-m}))-$separable when $k\le m-1$ (and, hence, $(t, 1/2)-$separable when $k  \leq m -t-2$).\\
  (c)  $  \mathcal{SV}(\gamma, n)$ is $(t,  \gamma/2^{t} )-$separable.\\
%  (c)  $  \mathcal{SV}(\gamma, n)$ is $(t,   \frac{\gamma  }{2^{t+1}} )-$separable.\\
  (d)   $ \mathcal{BCL}(\gamma, b, n)$ is $(t,     1-  2^{t+2}/(1+ \gamma)^b)-$separable.   In particular,  it is  $(t, 1/2)-$separable  for  $ b \geq (t+3)/ \log (1+ \gamma)= \Theta((t+1)/\gamma)$.
    }

\end{lemma}

}



\ignore{

Combining Theorem \ref{theorem1} and Lemma \ref{lemma3}, we immediately  get:


\begin{corollary}
\label{spee}
{\slshape  (a)   $ \mathcal{W}eak(k,n)$ is   $(t, 1)-$expressive when   $ k \leq n-t-2$,   and $(t, 2^{n-t-k-2} )-$expressive  when   $ n -t-2 < k \leq   n -1$. In  particular,  it's $(t, \frac{1}{2})-$expressive when $  k \leq n-t-1$. \\
  (b)  $\mathcal{B}lock(k,m,n)$ is $\left(t, \frac{1}{1 + 2^{t+2}\cdot \left(\frac{2^k-1}{2^m-2^k}\right)} \right)-$expressive. In particular, it is
  $(t,    \frac{1}{1+2^{3+t+k-m}})-$expressive when $k\le m-1$ (and, hence, $(t, \frac{1}{2})-$expressive when
  $k  \leq m -t-3$).\\
 (c)        $  \mathcal{SV}(\gamma, n)$ is $(t,   \frac{\gamma  }{2^{t+1}} )-$expressive.  \\
(d)   $  \mathcal{BCL}(\gamma, b, n)$ is $(t,     1-  \frac{2^{t+3} }{  (1+ \gamma)^b})-$expressive.   In particular, it's $(t,  \frac{1}{2})-$expressive for  $ b \geq \frac{t+4}{ \log (1+ \gamma)}= \Theta ( \frac{t+1}{\gamma} )$.

     }

\end{corollary}


}



\subsection{Implications to Traditional and Differential Privacy }

\ignore{

\mypar{ Impossibility of Weak Bit Extraction.}  {\color{red} new stuff, essentially stating that even $(t, \delta)$-weak bit extraction
impossible for our sources.  ???}

{\color{red}  It should be noted that  the result about  $(\mathcal{R}_n, \delta)$-secure  bit extraction is special case of the counterpart about  $(\mathcal{R}_n, \delta, 2^{-t})$-secure weak bit extraction   with $t=0$.   }
}

\mypar{  Impossibility of Traditional Privacy.}
From  Lemma \ref{lemma3} and  Corollary \ref{sep-privacy} (a)-(d), we conclude:

\begin{theorem}
   \label{imp}
   {\slshape For the following values of $ \delta$,   shown in Table~\ref{table1},  no $(\mathcal{R}_n, \delta)-$secure cryptographic primitive $P$ exists, where  $ \mathcal{R}_n \in  \{ \mathcal{W}eak(k, n), \mathcal{B}lock(m-1,m, n), \\  \mathcal{SV}( \gamma, n),  \mathcal{BCL}(\gamma, b, n)\}$ and $P \in \{$bit extractor, bit encryption scheme, weak bit commitment, bit $T$-secret sharing$\}$.
%(a)  No $( \mathcal{SV}( \gamma, n), \frac{\gamma}{4} )-$secure bit extractor (resp. encryption scheme ) exists. (b) No $(\mathcal{BCL}(\gamma, b, n),   1-  \frac{ 8 }{  (1+ \gamma)^b}   )-$secure bit extractor (resp. encryption scheme ) exists. In particular,  for  $b=\Omega(  \frac{t+4}{\gamma})$, no $(\mathcal{BCL}(\gamma, b, n),   \frac{1}{2}  )-$secure bit extractor (resp. encryption scheme ) exists. (c) If $ k< n-2$, then no  $ ( \mathcal{W}eak(k, n),   1 )-$secure bit extractor (resp. encryption scheme ) exists; If $ n-2 \leq k \leq n-1$, then no  $ ( \mathcal{W}eak(k, n),  2^{n-k-2}  )-$secure bit extractor (resp. encryption scheme ) exists.   In  particular,  if $ k \leq n-1$, then no  $ ( \mathcal{W}eak(k, n),  \frac{1}{2} )-$secure bit extractor (resp. encryption scheme ) exists.  (a') No $(  \mathcal{SV}( \gamma, n),     )-$secure  commitment exists.


\begin{table}[!h] \scriptsize  \renewcommand{\arraystretch}{1.8}
 \newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}
 \centering
 \begin{tabular}{|l|c|c|c|c|}  % {lccccccc}
\hline
 \backslashbox[20mm]{$\mathcal{R}_n$}{$P$} & bit extractor & \tabincell{c}{bit encryption\\ scheme}  & \tabincell{c}{weak bit \\ commitment} & bit $T$-secret sharing  \\ \hline
$ \mathcal{W}eak(k, n)$  & 1, if $k \leq n-2$ & 1, if $k \leq  n-2$ & 1, if  $k \leq n-3$ &   1, if  $k \leq n- \log T-2$ \\
\hdashline
 $\mathcal{W}eak(n-1, n)$    &  $\frac{1}{2}$ & $\frac{1}{2}$ & $\frac{1}{4}$ & $\frac{1}{2T}$  \\
\hline
 $\mathcal{B}lock(m-1, m,n)$ &  $\frac{1}{5}$ & $\frac{1}{5}$ & $\frac{1}{9}$ & $\frac{1}{4T+1}$  \\ \hline
 $ \mathcal{SV}( \gamma, n)$ & $\frac{\gamma}{2}$  & $\frac{\gamma}{2}$ & $\frac{\gamma}{4}$ & $\frac{\gamma}{2T}$ \\ \hline  % \hline
 $  \mathcal{BCL}(\gamma, b, n)$  & $\frac{1}{2}$, if $b \geq \frac{4}{\log(1+ \gamma)}$    &  $\frac{1}{2} $, if $b \geq \frac{4}{\log(1+ \gamma)}$  &   $\frac{1}{2}$, if $b \geq \frac{5}{\log(1+ \gamma)}$  &     $\frac{1}{2}$, if $b \geq \frac{  \log T +4}{\log(1+ \gamma)}$\\  \hline
   \end{tabular}
\setlength{\abovecaptionskip}{3pt}
\setlength{\belowcaptionskip}{-14pt}
\caption{Values of $ \delta $  for which  no $(\mathcal{R}_n, \delta)-$secure  cryptographic primitive  $P$ exists.\label{table1}}

\end{table}  }
\end{theorem}

We notice that, while the impossibility results for the block and BCL sources are new, the prior work of \cite{MP90,DOPS04} already obtained similar results for the weak  and SV sources. However,  our results still offer some improvements over the works of \cite{MP90,DOPS04}. First, unlike
the work of \cite{MP90}, our distinguisher is efficient (see Remark~\ref{efficient}), ruling out even computationally secure encryption, commitment, and secret sharing schemes. Second, unlike
the work of \cite{DOPS04}, our lower bound on $\delta$ does not depend on the sizes of ciphertext/commitment/shares. In particular, while \cite{DOPS04} used a bit-by-bit hybrid argument to show their impossibility results, our proof of Theorem~\ref{theorem1} used a more clever ``universal hashing trick''. More importantly, instead of focusing the entire proof on some specific weak/block/SV sources~\cite{MP90,DOPS04}, our impossibility results for such sources were obtained in a more modular manner, making these proofs somewhat more illuminating.




\mypar{ Impossibility of Differential Privacy with the Weak, Block and BCL sources.}
Now  we  apply  the impossibility results of differential privacy to the sources $\mathcal{W}eak(k, n)$, $\mathcal{B}lock(k, m, n)$,  and $\mathcal{BCL}(\gamma, b, n)$. In particular, by combining  Corollary  \ref{sep-privacy} (e.2)    with
 Lemma  \ref{lemma3} (a), (b), and (d), respectively, we get
\begin{theorem}\label{weak-imp,block-imp,bcl-imp}
{\slshape    For the following sources $\mathcal{R}_n $, no   $(\mathcal{R}_n,   \varepsilon)-$differentially private and $(U_n, \rho)$-accurate mechanisms for the Hamming weight queries  exist:  \\
 (a) $  \mathcal{W}eak(k, n)$ where $k \leq n -\log  (\varepsilon \rho)-6$;\\
(b)  $\mathcal{B}lock(k, m, n)$ where $k \leq m -\log  (\varepsilon \rho)-8$; \\
(c) $\mathcal{BCL}(\gamma, b, n)$ where  $b   \geq \frac{  \log ( \varepsilon \rho )  + 9 }{  \log(1+ \gamma)} = \Omega (  \frac{\log( \varepsilon \rho)+1}{ \gamma})$.

}

\end{theorem}
We discuss the (non-)implications to the SV source below, but notice the strength of these negative results the moment the source becomes a little bit more ``adversarial'' as compared to the SV source. In particular, useful mechanisms in differential privacy (called ``non-trivial'' by \cite{DLMV12}) aim to achieve utility $\rho$ (with respect to the uniform distribution) which only depends on the differential privacy $\varepsilon$, and not on the size $N$ of the database $D$. This means that the value $\log(\varepsilon \rho)$ is typically upper bounded by some constant $c=O(1)$. For such ``non-trivial'' mechanisms, our negative results say that differential privacy is impossible with (1) weak sources even when the min-entropy $k = n - O(1)$; (2) block sources even when the min-entropy $k = m - O(1)$; (3) BCL sources even when the number of interventions $b=\Omega(1)$.
So what prevented us from strong impossibility for the SV sources, as is expected given the feasibility results of \cite{DLMV12}? The short answer is that the separability of the SV sources given by Lemma \ref{lemma3} (c) is just not good enough to yield very strong results.
%, as we explain now.
We explain it in more detail in \cite{DY14}.

%\vspace{0.15cm}


\subsection{Comparing Impossibility Results for Traditional and Differential Privacy}

In this section, we compare the impossibility of traditional privacy and differential privacy (see Table~\ref{table2}). For traditional privacy,  we consider
 bit extractor, bit encryption scheme, weak bit commitment, and  bit $T$-secret sharing (i.e., set
$T = 2$ for concreteness). We observe that the impossibility results for differential privacy  are only marginally weaker than those for traditional privacy.
  \ignore{
  (e.g., set $T=2$ for concreteness).
  }

\begin{table}[ht] \scriptsize  \renewcommand{\arraystretch}{1.5}
 \newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}
 \centering
 \begin{tabular}{|l|c|c|}  % {lccccccc}
\hline ~~~~Source~  & Traditional Privacy $ \delta$   &  Differential Privacy $ \varepsilon $ \& Utility $ \rho$ \\ \hline  % \hline
%$ ~~\mathcal{W}eak(k, n)$~~ &~~  Impossible if $\delta \leq \frac{1}{4}$, even  if $k=n-1$ ~~& %~Impossible if $k \leq n - \log( \varepsilon \rho) - O(1)$~~\\ \hline
$ \mathcal{B}lock(k,m, n)$ & Impossible if $\delta \leq \frac{1}{9}$, even  if $k=m-1$ & Impossible if $k \leq m - \log( \varepsilon \rho) - O(1)$\\ \hline
$ \mathcal{SV}( \gamma, n)$ &  Impossible if  $\delta = O(  \gamma )$ &   \tabincell{c}{
Impossible if $\rho = O(\frac{1}{ \varepsilon}  )$, even for $U_n$
 \\ (Possible if $ \rho = poly_{1/(1-\gamma)}( \frac{1}{ \varepsilon}) \gg \frac{1}{\varepsilon}$) } \\ \hline  % \hline
$  \mathcal{BCL}(\gamma, b, n)$  &  \tabincell{c} {Impossible if $\delta = O(  \gamma )$, even if $b=0$;\\ Impossible if $ \delta \le \frac{1}{2} $ and $b = \Omega (\frac{1}{ \gamma}  )$} & Impossible if $ b = \Omega (  \frac{\log( \varepsilon \rho)+1}{ \gamma})$       \\ \hline
\end{tabular}
\setlength{\abovecaptionskip}{3pt}
\setlength{\belowcaptionskip}{-14pt}
\caption{Comparison about the Impossibility of Traditional  Privacy and Differential Privacy.\label{table2}}
\end{table}


\ignore{

{\color{red} Would it be better if we change the above table into the following one?  }

\begin{table}[ht]
 \newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}}
 \centering
{\color{red} \begin{tabular}{|l|c|c|}  % {lccccccc}
\hline ~~~~Source~  & Traditional Privacy $ \delta$   &  Differential Privacy $ \varepsilon $ \& Utility $ \rho$ \\ \hline  % \hline
%$ ~~\mathcal{W}eak(k, n)$~~ &~~  Impossible if $\delta \leq \frac{1}{4}$, even  if $k=n-1$ ~~& %~Impossible if $k \leq n - \log( \varepsilon \rho) - O(1)$~~\\ \hline
$ ~~\mathcal{B}lock(k,m, n)$~~ &~~  Impossible if $\delta \leq \frac{1}{9}$, even  if $k=m-1$ ~~& ~~Impossible if $k \leq m - \log( \varepsilon \rho) - 8$~~\\ \hline
$ ~~\mathcal{SV}( \gamma, n)$ ~~&  Impossible if  $\delta = \frac{\gamma}{4}$ &   \tabincell{c}{
Impossible if $\rho = O(\frac{1}{ \varepsilon}  )$, even for $U_n$
 \\ (Possible if $ \rho = poly_{1/(1-\gamma)}( \frac{1}{ \varepsilon}) \gg \frac{1}{\varepsilon}$) } \\ \hline  % \hline
$  ~~\mathcal{BCL}(\gamma, b, n)$~~  &  \tabincell{c} {~~Impossible if $\delta = O(  \gamma )$, even if $b=0$;~~\\ Impossible if $ \delta \le \frac{1}{2} $ and $b = \Omega (\frac{1}{ \gamma}  )$} & Impossible if $b   \geq \frac{  \log ( \varepsilon \rho )  + 9 }{  \log(1+ \gamma)}$       \\ \hline
\end{tabular}  }
\setlength{\abovecaptionskip}{5pt}
\caption{Comparison about the Impossibility of Traditional  Privacy and Differential Privacy.\label{table2}}
\end{table}



}





In particular, while a very ``structured'' (and, hence,     rather unrealistic) SV source is sufficient to guarantee loose, but non-trivial differential privacy, without guaranteeing (strong-enough) traditional privacy, once the source becomes more realistic (e.g., number of interventions $b$ becomes super-constant, or one removes the conditional entropy guarantee within different blocks), both notions of privacy become impossible {\em extremely quickly}. In other words, despite the surprising feasibility result of
\cite{DLMV12} regarding differential privacy with SV sources, the prevalent opinion that ``privacy is impossible with realistic weak randomness'' appears to be rather accurate.






%A more general version of Theorem \ref{imdp}
%\begin{theorem}

%{\slshape  For any $1\le t \le log(1/\varepsilon   )-2$, if a source $ \mathcal{R}_n$
% is $(t + \log  (\rho) + 4,  \frac{1}{2^t} )-$expressive, then no $(
%\mathcal{R}_n, \varepsilon )-$differentially private and $( U_n, \rho
%)$-accurate mechanism  for the Hamming weight queries exists.
%}


%\end{theorem}





\subsubsection*{Acknowledgments.}
The authors would like to thank  Benjamin Fuller,  Sasha Golovnev, Hamidreza Jahanjou, Zhoujun Li, Umut Orhan,  and Abhishek Samanta.
In particular, the authors  thank  Prof. Zhoujun Li very much for his great help about this paper. The authors also thank the anonymous reviewers for their helpful comments.
Yevgeniy Dodis was partially supported by gifts from VMware Labs and Google,
and NSF grants 1319051, 1314568, 1065288, and 1017471.
Yanqing Yao  was supported by   NSFC grants 61170189 and
61370126,    the Fund for the Doctoral
Program of Higher Education of China  20111102130003,  the Scholarship Award
for Excellent Doctoral Student granted by Ministry of Education
400618, and  CSC grant 201206020063.









\begin{thebibliography}{999999999} % 100 is a random guess of the total number of
%references
\setlength{\labelwidth}{0.6in}
%\addtolength{\leftmargin}{10em} % sets up alignment with the following line.
%\setlength{\marginparwidth}{3in}
\setlength{\itemindent}{0in}
%\setlength{\leftmargin}{-7in}
\bibitem[ACM$^+$14]{ACMPS14} Austrin, P., Chung, K.M.,   Mahmoody, M., Pass,  R., Seth, K.:   On the Impossibility of Cryptography with Tamperable Randomness. CRYPTO 2014,  LNCS  8616, 462-479 (2014)
\vspace{0.11cm}

\bibitem[ACRT99]{ACRT99} Andreev,  A.E., Clementi, A.E.F.,   Rolim, J.D.P.,   Trevisan, L.:  Weak
random sources, hitting sets, and BPP simulations.    SIAM J. Comput.  28(6),  2103-2116
(1999)
\vspace{0.11cm}
\bibitem[Blu86]{B86}  Blum, M.:  Independent unbiased coin-flips from a correclated biased source-a finite state Markov
chain.  Combinatorica 6(2),  97-108 (1986)
\vspace{0.11cm}
\bibitem[BD07]{BD07}  Bosley,  C.,  Dodis, Y.:  Does privacy require true randomness?  TCC 2007,  LNCS 4392,   1-20  (2007)
\vspace{0.11cm}
\bibitem[BDK$^+$05]{BDK$^+$05} Boyen, X.,  Dodis, Y.,  Katz, J.,  Ostrovsky, R.,  Smith,  A.:  Secure remote
authentication using biometric data.  EUROCRYPT 2005,   LNCS 3494,  147-163  (2005)
\vspace{0.11cm}
\bibitem[BH05]{BH05} Barak, B.,  Halevi,  S.:  A model and architecture for pseudo-random generation with applications
to /dev/random. Proceedings of the 12th ACM conference on Computer and communications security,    203-212 (2005)
\vspace{0.11cm}
\bibitem[BST03]{BST03} Barak, B.,  Shaltiel, R.,    Tromer,  E.:   True random number generators secure in a
changing environment. In  Proceedings of the 5th Cryptographic Hardware and Embedded Systems,  LNCS  2779,  166-180  (2003)
\vspace{0.11cm}
\bibitem[CFG$^+$85]{CFG$^+$85} Chor, B.,  Friedman, J., Goldreich,  O.,  H{\aa}stad,  J.,  Rudich,  S.,   Smolensky,  R.:
 The Bit Extraction Problem
or $t$-resilient Functions. In  the 26th Annual Symposium on Foundations of Computer Science, 396-407  (1985)

\bibitem[CG88]{CG88} Chor, B.,    Goldreich, O.:   Unbiased bits from sources of weak randomness and
probabilistic communication complexity.  SIAM J. Comput. 17(2),  230-261  (1988)
\vspace{0.11cm}
\bibitem[CW79]{CW79} Carter,   J.L.,         Wegman,  M.N.:    Universal Classes of Hash Functions.  J. Comput. Syst. Sci.  18(2),  143-154 (1979)
\vspace{0.11cm}
\bibitem[Dod01]{D01} Dodis,  Y.:   New Imperfect Random Source with Applications to Coin-Flipping.   ICALP 2001, LNCS 2076,   297-309 (2001)
\vspace{0.11cm}
\bibitem[DKRS06]{DKRS06} Dodis, Y.,  Katz, J.,  Reyzin, L.,  Smith, A.:   Robust fuzzy extractors
and authenticated key agreement from close secrets.   CRYPTO 2006,
 LNCS  4117,   232-250 (2006)
\vspace{0.11cm}
\bibitem[DLMV12]{DLMV12} Dodis,  Y., L\'{o}pez-Alt, A.,  Mironov, I., Vadhan, S.P.:   Differential Privacy with Imperfect Randomness.  CRYPTO 2012,   LNCS 7417,   497-516 (2012)
\vspace{0.11cm}
\bibitem[DMNS06]{DMNS06} Dwork, C.,  McSherry, F.,     Nissim, K.,   Smith, A.:   Calibrating noise to
sensitivity in private data analysis.   TCC 2006,   LNCS 3876,  265-284 (2006)
\vspace{0.11cm}
\bibitem[DOPS04]{DOPS04} Dodis, Y.,  Ong, S.J.,   Prabhakaran, M.,   Sahai, A.:  On the
(im)possibility of cryptography with imperfect randomness.    45th Symposium on Foundations of Computer Science,   196-205 (2004)
\vspace{0.11cm}
\bibitem[DORS08]{DORS08} Dodis, Y., Ostrovsky, R., Reyzin, L.,   Smith,  A.:   Fuzzy extractors: How to
generate strong keys from biometrics and other noisy data. SIAM J.  Comput. 38(1),  97-139 (2008)
\vspace{0.11cm}
\bibitem[DS02]{DS02} Dodis, Y.,  Spencer, J.:   On the (non)Universality of the One-Time Pad.  43rd Symposium on Foundations of Computer Science, 376-385 (2002)
    \vspace{0.11cm}
\bibitem[DY14]{DY14}   Dodis, Y.,  Yao,  Y.Q.: Privacy with Imperfect Randomness. IACR Cryptology ePrint Archive 2014: 623 (2014)
   \vspace{0.11cm}
\bibitem[GKR04]{GKR04} Gennaro,  R., Krawczyk, H., Rabin,  T.:   Secure hashed diffie-hellman over non-ddh
groups. In Christian Cachin and Jan Camenisch, editors,   EUROCRYPT
2004,  LNCS 3027, 361-381 (2004)
\vspace{0.11cm}
\bibitem[Kra10]{K10} Krawczyk, H.:   Cryptographic Extraction and Key Derivation: The HKDF Scheme.  CRYPTO 2010,   LNCS 6223,  631-648  (2010)
\vspace{0.11cm}
\bibitem[LLS89]{LLS89} Lichtenstein, D., Linial, N., Saks,  M.E.:   Some extremal problems arising form discrete control processes.
    Combinatorica   9(3),  269-287 (1989)
    \vspace{0.11cm}
\bibitem[MP90]{MP90} McInnes, J.L., Pinkas, B.:   On the impossibility of private key cryptography
with weakly random keys.   CRYPTO 1990,
 LNCS 537,  421-435 (1991)
\vspace{0.11cm}
\bibitem[MW97]{MW97} Maurer,   U.M.,   Wolf,  S.:   Privacy amplification secure against active adversaries.  CRYPTO 1997,  LNCS 1294,  307-321 (1997)
\vspace{0.11cm}
\bibitem[RVW04]{RVW04} Reingold, O., Vadhan, S., Widgerson,  A.:    No Deterministic Extraction from
Santha-Vazirani Sources: a Simple Proof. http://windowsontheory.org/2012/02/21/nodeterministic-extraction-from-santha-vazirani-sources-a-simple-proof/  (2004)
\vspace{0.11cm}
\bibitem[SV86]{SV86} Santha,  M.,  Vazirani,  U.V.:   Generating quasi-random sequences from semirandom
sources.    J. Comput. Syst. Sci. 33(1),  75-87 (1986)
\vspace{0.11cm}
\bibitem[vN51]{vN51} Neumann,  J.v.:  Various techniques used in connection with random digits. In  National Bureau of
Standards, Applied Math. Series  12,  36-38 (1951)
\vspace{0.11cm}
\bibitem[VV85]{VV85} Vazirani,  U.V., Vazirani,  V.V.:   Random polynomial time is equal to slightly random
polynomial time.  26th Annual Symposium on Foundations of Computer Science,   417-428 (1985)
\vspace{0.11cm}
\bibitem[Zuc96]{Zuc96} Zuckerman,  D.:    Simulating BPP using a general weak random source.  Algorithmica
16(4/5), 367-391 (1996)




\end{thebibliography}


\ignore{

\newpage
\appendix


\section{Postponed Proofs}


\subsection{Proof of Theorem~\ref{expp}}\label{app:expp}

\begin{proof}

\noindent
(a) Assume that there exists a  $(\mathcal{R}_n, \delta)$-secure bit extractor  $\textsf{Ext}$.
  Define $f( \mathbf{r}) \overset{def}{ =}  \textsf{Ext}(\mathbf{r})$ and  $g(\mathbf{r}) \overset{def}{ =} 1- \textsf{Ext}(\mathbf{r})$.  Since  for all  $\mathbf{r} \in \{0, 1\}^n$,  it holds that  $ \textsf{Ext}(\mathbf{r}) \neq    1- \textsf{Ext}(\mathbf{r})$, we get $  \Pr \limits_{   \mathbf{r} \leftarrow U_n}   [ f( \mathbf{r} ) \neq g ( \mathbf{r} )   ] =1 = \frac{1}{2^0}$.  Definition \ref{exp}  implies that  there exists
a distribution $R \in \mathcal{R}_n$ such that $ \textsf{SD}(f(R), g(R)  )  \geq  \delta$.   Therefore,
$$|  \Pr [\textsf{Ext}(R)=1] - \Pr [\textsf{Ext}(R)=0]   |  =  \textsf{SD}(f(R), g(R)  )   \geq  \delta,$$
which is a contradiction.


\vspace{1ex}\noindent
(b) Assume that there exists a  $(\mathcal{R}_n, \delta)$-secure bit encryption scheme.   Define $f(\mathbf{r}) \overset{def}{ =}  \textsf{Enc}_{\mathbf{r} }(0)$ and  $g(\mathbf{r}) \overset{def}{ =} \textsf{Enc}_{\mathbf{r} }(1)$.  Since for   all secret keys $\mathbf{r} \in \{0, 1\}^n$,  it holds that  $\textsf{Enc}_{\mathbf{r} }(0)  \neq  \textsf{Enc}_{\mathbf{r} }(1)$, we have
$\Pr \limits_{   \mathbf{r} \leftarrow U_n}  [ f( \mathbf{r} ) \neq g ( \mathbf{r} )   ] = 1 = \frac{1}{2^0}$.  Definition \ref{exp}  implies that  there exists a distribution $R \in \mathcal{R}_n$ such that $ \textsf{SD}(f(R), g(R)  ) \geq  \delta$, which is in contradiction to  $ \textsf{SD}(f(R), g(R)  ) < \delta$.

\vspace{1ex}\noindent
(c) Assume that there exists a    $(\mathcal{R}_n, \delta)$-secure weak bit commitment.    Define $f(\mathbf{r}) \overset{def}{ =}  \textsf{Com}(0; \mathbf{r})$ and  $g(\mathbf{r}) \overset{def}{ =} \textsf{Com}(1; \mathbf{r})$.  Since $\Pr  \limits_{ \mathbf{r} \leftarrow U_n }[\textsf{Com}(0; \mathbf{r})  \neq \textsf{Com}(1;  \mathbf{r})   ] \geq \frac{1}{2}$, there exists
a distribution $R \in \mathcal{R}_n$ such that $ \textsf{SD}(f(R), g(R))  \geq  \delta$, which is in contradiction to  $ \textsf{SD}(f(R), g(R)  ) < \delta$.



\vspace{1ex}\noindent
(d)   Assume that there exists a   $(\mathcal{R}_n, \delta)$-secure bit $T$-secret sharing.     Let $t=\log T$.   Then for all $ \mathbf{r} \in \{0, 1\}^n$,
 \begin{align*}
&  (  \textsf{Share}_1 (0; \mathbf{r}),   \ldots,  \textsf{Share}_T (0; \mathbf{r}) ) \neq  (  \textsf{Share}_1(1; \mathbf{r}),   \ldots,  \textsf{Share}_T(1; \mathbf{r}))
 \\&
  \Rightarrow  there ~ exists ~ j = j(\mathbf{r})~ such ~that ~ \textsf{Share}_j(0; \mathbf{r}) \neq  \textsf{Share}_j(1; \mathbf{r}).\\&
\Rightarrow   there ~exists ~ j^* \in [T] ~ such~ that~  | \{ \mathbf{r} \mid  j(\mathbf{r}) = j^* \}  |    \geq \frac{2^n}{T} =  2^{n-t}.
\end{align*}
 Define $f(\mathbf{r}) \overset{def}{ =}  \textsf{Share}_{j^*}(0; \mathbf{r})$ and  $g(\mathbf{r}) \overset{def}{ =} \textsf{Share}_{j^*}(1; \mathbf{r})$.
Then $  \Pr  \limits_{ \mathbf{r} \leftarrow U_n } [f ( \mathbf{r}) \neq g ( \mathbf{r})] \geq \frac{1}{2^t}$. Therefore, there exists
a distribution $R \in \mathcal{R}_n$ such that $ \textsf{SD}(f(R), g(R)  ) \\ \geq  \delta$, which is in contradiction to  $ \textsf{SD}(f(R), g(R)  ) < \delta$.


%\rightline { $\Box$ }

\end{proof}


 \ignore{
 \subsection{Proof of Theorem \ref{imdp}}\label{app:imdp}
}


\subsection{Proof of Theorem \ref{theorem1}}\label{app:theorem1}

\begin{proof}
 Suppose that $f, g: \{ 0, 1\}^n \rightarrow \mathcal{C}$ are two  arbitrary functions  such that $ \Pr \limits_{   \mathbf{r} \leftarrow U_n}   [ f( \mathbf{r} ) \neq g ( \mathbf{r} )   ]  \geq \frac{1}{2^t}$.   Let $ S =  \{ \mathbf{r} \in \{0, 1\}^n \mid f( \mathbf{r}  ) \neq  g( \mathbf{r}  )   \}$.  By assumption, $ |S| \geq 2^{n-t}$.

To build intuition, let's start with the special case where $\mathcal{C} = \{0, 1\}$, in which case we will even show that $(t,\delta)$-separability is enough (i.e., no need to increase $t$ by $1$).
For $ \alpha, \beta \in \{0, 1\}$,   denote $ S_{\alpha \beta} = \{ \mathbf{r} \in \{0, 1\}^n \mid f(\mathbf{r}) = \alpha  ~ and ~ g(\mathbf{r}) = \beta  \}$.

The distinguisher $\textsf{Eve}$ is defined as $\textsf{Eve}(x) = 1 \Leftrightarrow x=0$.     Without loss of generality, assume that
$|S_{01}| \geq | S_{10}|$.
%$|S_{01}| \geq \max(   | S_{10}  |,  2^{n-t-1} )% \geq \max(   | S_{10}  |, 2^{n-t-1} )$.
Denote $G \overset{def}{=} S_{01}$ and $B \overset{def}{=} S_{10}$.
Since $\mathcal{R}_n$ is  $( t,  \delta  )-$separable and $|G\cup B|\ge 2^{n-t}$, there exists a distribution $R \in \mathcal{R}_n$
such that $|\Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in G] - \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in B]~| \geq  \delta$. That is,
$  |\Pr \limits_{ \mathbf{r} \leftarrow R }  [\mathbf{r} \in S_{01}]  -  \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in S_{10}]~|  \geq \delta$.
Therefore,
 \begin{align*}
&\textsf{SD}(f(R), g(R))
\geq |\Pr \limits_{ \mathbf{r} \leftarrow R }[ \textsf{Eve}(f(\mathbf{r})) = 1] -  \Pr \limits_{ \mathbf{r} \leftarrow R }[ \textsf{Eve}(g( \mathbf{r}  ) ) = 1]~| \\&
~~~~~~~~~~~~~~~~~~~~= |\Pr \limits_{ \mathbf{r} \leftarrow R }[ f(\mathbf{r}) =0 ] -  \Pr \limits_{ \mathbf{r} \leftarrow R }[ g( \mathbf{r}   ) = 0]~| \\&
~~~~~~~~~~~~~~~~~~~~= | \Pr \limits_{ \mathbf{r} \leftarrow R }  [\mathbf{r} \in S_{01}]  -  \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in S_{10}]~ | \\&
~~~~~~~~~~~~~~~~~~~~\geq \delta.
\end{align*}



In the following, we analyze the general case.  We'll need to use the notion of universal hash function family \cite{CW79} with a single bit output. Recall that
  $ \mathcal{H} = \{ h \mid h:  \mathcal{C} \rightarrow \{0, 1\}  \}$  is a family of universal hash functions if  for all $ z \neq z'$,   $  \Pr \limits_{  h  \leftarrow U_{\mathcal{H}} }[ h(z) \neq  h(z')  ] = \frac{1}{2} $. Such families are known to exist for any universe $ \mathcal{C} $ and can be made  efficient in $n$  if $  \mathcal{C} \subseteq \{0, 1\}^{poly (n)}$.

For $ \alpha, \beta \in \{0, 1\}$ and $h \in \mathcal{H}$,   denote $$ S_{\alpha \beta}(h)= \{ \mathbf{r} \in S \mid h( f( \mathbf{r})) = \alpha  ~ and ~  h (g(\mathbf{r}) )= \beta  \}.$$
  Then
\begin{align*}
& \mathbb{E}_{ h  \leftarrow U_{\mathcal{H}}} [|S_{01}(h)   |+|S_{10}(h) |] =\mathbb{E}_ { h  \leftarrow U_{\mathcal{H}} } [  \sum \limits_{ \mathbf{r} \in S }  \chi_{S_{01}(h)   \cup S_{10}(h)  } (\mathbf{r}  )    ]\\&
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  = \sum \limits_{ \mathbf{r} \in S }  \Pr \limits_{ h \leftarrow U_{\mathcal{H}} } [ \mathbf{r} \in   S_{01}(h)   \cup S_{10}(h)  ] \\&
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  = \sum \limits_{ \mathbf{r} \in S }  \Pr \limits_{ h \leftarrow U_{\mathcal{H}} } [ h(f(  \mathbf{r} ))  \neq h(g(  \mathbf{r} ))]\\&
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  = \frac{|S|}{2},
\end{align*}
where $\chi_{S_{01}(h)  \cup S_{10}(h) }$  denotes the characteristic function of the set $ S_{01}(h)  \cup S_{10}(h)$.

Hence, there exists a fixed hash function $h^* \in \mathcal{H}$ such that
$$ | S_{01} (h^*) \cup   S_{10} (h^*)  |  \geq \frac{|S|}{2} \geq  2^{n-t-1}.$$
$\textsf{Eve}$ is defined as $\textsf{Eve}( C) = 1 \Leftrightarrow h^*(C) =0$, for all $C \in \mathcal{C}$.   Without loss of generality, assume that
$|S_{01} (h^*)  | \geq | S_{10} (h^*)  |$.
%$|S_{01} (h^*)  | \geq \max(   | S_{10} (h^*)  |, 2^{n-t-2} )$.
Denote $ G \overset{def}{=} S_{01} (h^*)  $ and $ B \overset{def}{=} S_{10} (h^*) $.
Since $\mathcal{R}_n$ is  $(t+1,  \delta)-$separable, there exists a distribution $R' \in \mathcal{R}_n$
such that $|\Pr \limits_{ \mathbf{r} \leftarrow R' }[\mathbf{r} \in G]-  \Pr \limits_{ \mathbf{r} \leftarrow R' }[\mathbf{r} \in B]~| \geq \delta.$ That is,
 $$|\Pr \limits_{ \mathbf{r} \leftarrow R' }  [\mathbf{r} \in S_{01}(h^*)]  -  \Pr \limits_{ \mathbf{r} \leftarrow R' }[\mathbf{r} \in S_{10}(h^*)]~|   \geq \delta.$$  Hence,
 \begin{eqnarray*}
\textsf{SD}(f(R'), g(R'))&
\geq& |\Pr \limits_{ \mathbf{r} \leftarrow R' }[\textsf{Eve}(f(\mathbf{r})) = 1] -  \Pr \limits_{ \mathbf{r} \leftarrow R' }[ \textsf{Eve}(g(\mathbf{r})) = 1]~| \\&
= &|\Pr \limits_{ \mathbf{r} \leftarrow R' }[ h^* (f(\mathbf{r})) =0 ] -  \Pr \limits_{ \mathbf{r} \leftarrow R' }[ h^* (g( \mathbf{r}   )) = 0]~| \\ &
= & | \Pr \limits_{ \mathbf{r} \leftarrow R' }  [\mathbf{r} \in S_{01}(h^*)]  -  \Pr \limits_{ \mathbf{r} \leftarrow R' }[\mathbf{r} \in S_{10}(h^*)]~ | \\&
\geq&
 \delta.
\end{eqnarray*}

Therefore,  the source $\mathcal{R}_n$ is $(t, \delta)-$expressive.


%\rightline { $\Box$ }
\end{proof}

\subsection{Proof of Lemma \ref{weakext}}\label{app:weakext}

\begin{proof}  We only prove that non-separability implies weak bit extraction, as the converse is clear because all our steps will be ``if and only if''.

Since $\mathcal{R}_n$ is \underline{not} $(t, \delta)$-separable, then there are two sets $G$ and $B$ such that $G\cap B= \emptyset$, $|G\cup B|\ge 2^{n-t}$ and for all $R\in \mathcal{R}_n$, we have
$|\Pr \limits_{\mathbf{r} \leftarrow R } [ \mathbf{r} \in G] - \Pr \limits_{\mathbf{r} \leftarrow R } [\mathbf{r} \in B]| <  \delta$. Define

\begin{equation}
  \textsf{Ext} (\br) \overset{def}{=}   \left\{
\begin{aligned}
1, & ~~ \mbox{if} ~ \br\in G; \nonumber\\
0, & ~~ \mbox{if} ~  \br \in B; \nonumber\\
\bot, & ~~ \mbox{otherwise}.
\end{aligned}
\right.
\end{equation}
This is well defined since $G\cap B = \emptyset$, and it satisfies properties (a) and (b) of weak bit extractor, since $\delta  > |\Pr \limits_{\mathbf{r} \leftarrow R }[\mathbf{r} \in G] - \Pr \limits_{\mathbf{r} \leftarrow R }[\mathbf{r} \in B]| = |\Pr \limits_{\mathbf{r} \leftarrow R } [ \textsf{Ext} (\mathbf{r}) =1] - \Pr \limits_{\mathbf{r} \leftarrow R }[ \textsf{Ext} (\mathbf{r}) =0]|$, while $\Pr \limits_{\mathbf{r} \leftarrow U_n } [\textsf{Ext}(\mathbf{r})\neq \bot] = |G\cup B|/2^n \ge 2^{n-t}/2^n = 2^{-t}$.

\end{proof}



% \flushright { $\Box$ }


\subsection{Proof of Lemma \ref{lemma3}}\label{app:lemma3}

\begin{proof}  Let $G, B \subseteq \{0, 1\}^n$ where $G \cap B = \emptyset$ and $|G \cup B| \geq 2^{n-t}$. Without loss of generality, assume that $|G| \geq |B|$.  Then  $|G| \geq  2^{n-t-1}$.
\vspace{0.15cm}

\vspace{1ex}\noindent
(a) $\mathbf{Case~1}$:    Assume that $ k \leq n -t-1$.     Pick any $S \subset \{0, 1\}^n$ of size   $|S|= 2^{k}$ such that $S  \subseteq  G$. Then
 $ \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in B]  = 1- 0 =1. $

 $\mathbf{Case~2}$:    Assume that $ n -t -1 <  k  \leq n -1$.

$~~\mathbf{Case~2.1}$:   Suppose that $|G| \leq 2^{k}$.   Then $  |B| + 2^k \leq |G| + 2^k \leq 2^{k} + 2^{k} \leq 2^n$.     Choose a set $S \subset \{0, 1\}^n$ of size $|S|= 2^{k}$ such that $G \subseteq S$ and $ B \cap S = \emptyset$.  Then $$ \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow  U_S  }[ \mathbf{r} \in B]  = \frac{ 1}{2^{k}} \cdot |G|  - 0 \geq 2^{n-t-k-1}. $$



$~~\mathbf{Case~2.2}$:  Now assume that $|G| > 2^{k}$.  Then pick any $S \subset \{0, 1\}^n$ of size   $|S|= 2^{k}$ such that $S \subset G$. Then
%$$ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]= \frac{1+ \gamma}{2^n} \cdot |S| + \frac{1- \gamma}{2^n} \cdot |G \setminus  S| - \frac{1- \gamma}{2^n} \cdot |B|  $$
$ \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow U_S }[ \mathbf{r} \in B]  = 1- 0 =1.  $

% From \cite{3}, we get that there exists a  distribution $R  \in  \mathcal{SV}(\gamma, n)$  such that  $ \frac{\Pr \limits_{ \mathbf{r} \leftarrow R }[ \mathbf{r} \in G ]}{  \Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in B ]  }  \geq (1 + \gamma) \cdot \frac{|G|}{|B|} \geq  (1 + \gamma) \cdot \frac{  2^{n-t}}{2^n}$

 Assume that $k \leq n-t$.    If $ k \leq  n-t-1$,  it
 can be reduced to Case 1. Otherwise, it can be reduced to Case 2.






 %Let $S$ be the subset of $  \{0, 1\}^n$  such that $|S|=2^{n-1}$. Let $R= U_S$. Then  $ \Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in G  ] \geq \frac{2^{n-t}}{2^{n-1}}$.  Therefore,   $ \frac{\Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in G  ] }{\Pr \limits_{ \mathbf{r} \leftarrow R  }[ \mathbf{r} \in B  ]} \geq \frac{\frac{N}{2^{n-1}}  }{1}= \frac{N}{2^{n-1}}$.


\vspace{1ex}\noindent
(b) Define $R$ as follows. $\Pr[R=r]=q$ when $r\not\in G$, and $\Pr[R=r]=q(2^m-1)/(2^k-1)$ when $r\in G$, where $q$ is chosen such that $(2^n - |G|)\cdot q + |G|\cdot q(2^m-1)/(2^k-1) =1$, which is equivalent to
\begin{equation}\label{temp1}
q\left(|G|\cdot \frac{2^m - 2^k}{2^k-1} + 2^n \right) = 1
\end{equation}
First, we claim that $R$ is a valid $n$-bit $(k,m)$-Block-Source. For this, we show a slightly stronger statement (see Footnote~\ref{foot:sv}):  for every $i\in [n/m]$ and $s_1,\ldots,s_{i-1},\\s_{i+1},\ldots,s_{n/m}\in \{0,1\}^m$, we have
$$\mathbf{H}_\infty( R_i\mid R_1\ldots R_{i-1} R_{i+1} \ldots R_{n/m}= s_1\ldots s_{i-1}s_{i+1} \ldots s_{n/m}) \geq k.$$
(Correspondingly,   $\mathbf{H}_\infty( R_i\mid R_1\ldots R_{i-1}= s_1\ldots s_{i-1}) \geq k.$)


Indeed, for every $s_i\in \{0,1\}^m$,
\ignore{
\begin{eqnarray*}
\Pr [R_i=s_i &\mid & R_1\ldots R_{i-1} R_{i+1} \ldots R_{n/m}= s_1\ldots s_{i-1}s_{i+1} \ldots s_{n/m}]  \\ &=& \frac{\Pr [R_1\ldots R_{i-1} R_i R_{i+1} \ldots R_{n/m}= s_1\ldots s_{i-1}s_i s_{i+1} \ldots s_{n/m}]}{\sum_{s_i'\in \{0,1\}^m} \Pr [R_1\ldots R_{i-1} R_i R_{i+1} \ldots R_{n/m}= s_1\ldots s_{i-1}s_i' s_{i+1} \ldots s_{n/m}]}\\
&\le& \frac{q(2^m-1)/(2^k-1)}{q(2^m-1)/(2^k-1) + q(2^m-1)} = 2^{-k},
\end{eqnarray*}
}
\begin{align*}
&~~~~\Pr [R_i=s_i \mid  R_1\ldots R_{i-1} R_{i+1} \ldots R_{n/m}= s_1\ldots s_{i-1}s_{i+1} \ldots s_{n/m}]  \\ &
= \frac{\Pr [R_1\ldots R_{i-1} R_i R_{i+1} \ldots R_{n/m}= s_1\ldots s_{i-1}s_i s_{i+1} \ldots s_{n/m}]}{\sum_{s_i'\in \{0,1\}^m} \Pr [R_1\ldots R_{i-1} R_i R_{i+1} \ldots R_{n/m}= s_1\ldots s_{i-1}s_i' s_{i+1} \ldots s_{n/m}]}\\&
\leq  \frac{q(2^m-1)/(2^k-1)}{q(2^m-1)/(2^k-1) + q(2^m-1)} = 2^{-k},
\end{align*}



as claimed.

Next, since $|G|\ge |B|$, we have
$$| \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in G] - \Pr \limits_{ \mathbf{r} \leftarrow R }[\mathbf{r} \in B]~| = |G|\cdot \frac{q(2^m-1)}{2^k-1} - |B|\cdot q\ge q\cdot |G|\cdot \frac{2^m-2^k}{2^k-1}.$$
Comparing to Equation~(\ref{temp1}) and letting $\alpha = q\cdot |G|\cdot \frac{2^m-2^k}{2^k-1}$, $\beta = q\cdot 2^n$, we need to lower bound $\alpha$ subject to the constraints: (1) $\alpha+\beta=1$; (2) $\beta = \alpha\cdot  \frac{(2^k-1)2^n}{(2^m-2^k)|G|} \le \alpha \cdot \frac{2^{t+1}(2^k-1)}{2^m-2^k}$, where we used  $|G| \geq  2^{n-t-1}$. Combining (1) and (2), we get
$$1 = \alpha + \beta \le \alpha\left(1+ 2^{t+1} \cdot \frac{2^k-1}{2^m-2^k}\right),$$
which solves precisely to the lower bound on $\alpha$  claimed in part (b).

When $k\le m-1$, we get $(2^k-1)/(2^m-2^k) \leq  2^{k}/2^{m-1} = 2^{k-m+1}$, which gives the claimed bound
$$\frac{1}{1 + 2^{t+1}\cdot \left(\frac{2^k-1}{2^m-2^k}\right)}\ge \frac{1}{1+2^{2+t+k-m}}.$$

\vspace{1ex}\noindent
(c) We simply use the bound from part (b) for the special case when $m=1$ and $2^{-k} = (1+\gamma)/2$.
Then $2^k-1 = (1-\gamma)/(1+\gamma)$, $2^m-2^k = 2 - 2/(1+\gamma) = 2\gamma/(1+\gamma)$, and we get
 $(t,\delta)$-separability with
 $$\delta = \frac{1}{1+2^{t+1} \cdot \frac{1-\gamma}{2\gamma}} = \frac{\gamma}{2^t - \gamma(2^t-1)}\ge \frac{\gamma}{2^t},~\mbox{since}~t\ge 0.$$

\ignore{
 In proving Lemma \ref{lemma3}(b), we use a notion called  the  $ \gamma-$biased  halfspace source \cite{DOPS04},    which was  implicitly defined by
\cite{RVW04}.


\begin{definition}

   Given $S  \subset \{0, 1\}^n$ of size $ |S| = 2^{n-1}$, and  $ 0 \leq \gamma < 1$.
The  distribution  $H_S(\gamma, n  )$ over $ \{0, 1\}^n  $   is defined as

\begin{equation}
 R \equiv H_S(\gamma, n) \overset{def}{=}   \left\{
\begin{aligned}
\Pr[R= \mathbf{r}] = (1+  \gamma) \cdot 2^{-n}, & ~~ if ~ \mathbf{r} \in S; \nonumber\\
\Pr[R= \mathbf{r}] = (1-  \gamma) \cdot 2^{-n}, & ~~ otherwise. \nonumber\\
\end{aligned}
\right.
\end{equation}

The $\gamma$-biased halfspace source $\mathcal{H}(\gamma, n)$  is defined as  $$\mathcal{H}(\gamma, n) \overset{def}{=} \{ H_S(\gamma, n)  \mid  S \subseteq \{0, 1\}^n ~and~ |S| = 2^{n-1} \}.     $$


\end{definition}





\begin{claim}
\label{his}


(\cite{DOPS04,RVW04}) {\slshape  For any $n \in \mathbb{Z}^+$ and $  0 \leq \gamma < 1$, $ \mathcal{H}(\gamma, n)  \subset \mathcal{SV}(\gamma, n)$.  }

\end{claim}

Therefore, we only  need to choose a subset $S$ such that $ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]  \geq   \frac{\gamma}{2^t} $.




$  \mathbf{Case~1}$:  Suppose that $|G| \leq 2^{n-1}$.   Then $  |B| + 2^{n-1} \leq |G| + 2^{n-1}  \leq 2^n$.
Choose a set $S \subset \{0, 1\}^n$ of size $|S|= 2^{n-1}$ such that $G \subseteq S$ and $ B \cap S = \emptyset$.  Then $$ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]  = \frac{ 1+ \gamma}{2^n} \cdot |G| - \frac{ 1- \gamma}{2^n} \cdot |B|   =   \frac{|G|-|B|  }{2^n  }   +  \gamma \cdot  \frac{|G|+|B|  }{2^n } \geq  \gamma \cdot \frac{ 2^{n-t}}{2^n} = \frac{\gamma}{2^t}.$$



$  \mathbf{Case~2}$:  Now assume that $|G| > 2^{n-1}$. Pick any $S \subset \{0, 1\}^n$ of size   $|S|= 2^{n-1}$ such that $S \subset G$. Then
$ |S| = | \{0, 1\}^n  \setminus  S | \geq | G \setminus  S |$.
%$$ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]= \frac{1+ \gamma}{2^n} \cdot |S| + \frac{1- \gamma}{2^n} \cdot |G \setminus  S| - \frac{1- \gamma}{2^n} \cdot |B|  $
 \begin{align*}
&\Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B] = \frac{1+ \gamma}{2^n} \cdot |S| + \frac{1- \gamma}{2^n} \cdot |G \setminus  S| - \frac{1- \gamma}{2^n} \cdot |B|\\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~= \frac{1- \gamma}{2^n} \cdot ( \frac{1+ \gamma }{ 1- \gamma}   \cdot |S| + | G \setminus  S  | -   |B|) \\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~= \frac{1- \gamma}{2^n} \cdot (  |S| + |G \setminus  S| -  |B| + \frac{2 \gamma}{1- \gamma}  \cdot |S|  )  \\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~\geq \frac{1- \gamma}{2^n} \cdot [ ( |S| + |G \setminus  S|) -  |B| +  \frac{ \gamma}{1- \gamma}  \cdot  (|S|+  |G \setminus  S|   )]\\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = \frac{1- \gamma}{2^n} \cdot [ ( |G| -  |B| ) +  \frac{ \gamma}{1- \gamma}  \cdot  |G|]\\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~\geq   \frac{1- \gamma}{2^n} \cdot \frac{ \gamma}{1- \gamma}  \cdot  2^{n-t-1} \\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = \frac{\gamma}{2^{t+1}}.
\end{align*}
}

\vspace{1ex}\noindent
(d) We start by recalling the following auxiliary result from \cite{D01}.

 Given a Boolean function $f_e: \{0, 1\}^n \rightarrow  \{0, 1\}$, it is associated  with an event $E$ such that ``$E$  happens $ \Longleftrightarrow  f_e(\mathbf{x}) =1$", where $\mathbf{x} \in  \{0, 1\}^n$.  The {\slshape  natural probability  $p$} of  $E$  is defined as
the probability that $E$ happens for an ideal
source (in our case, emitting $n$ perfect unbiased bits).  More formally,
$$  p= \Pr \limits_{  \mathbf{r}  \leftarrow U_n} [f_e(\mathbf{r}  )=1] = \Pr \limits_{  \mathbf{r}  \leftarrow U_n} [ E~ happens ].  $$
We then say that  $E$ (or $f_e$) is $p$-sparse. We define  the set of  all  $p$-sparse events (or  Boolean functions) as  $ \mathcal{E}$.

We view the  source $ \mathcal{BCL}( \gamma, b, n)$ as an adversary  $ \mathcal{A}$ who can influence the ideal behavior  of the source by applying
rules (A) and (B) of Definition \ref{bcldef}.     Our goal is to see whether  our adversary $ \mathcal{A}  $  has enough power to significantly influence
the  occurrence of the event $E$.  For a given number of interventions $b$, to obtain the largest probability of ``success" that  $ \mathcal{A}$ can  achieve (i.e.,
the largest probability that any $p$-sparse event $E$ happens for  $ \mathcal{BCL}( \gamma, b, n)$), we first study the complement notion of
 ``smallest probability of failure" and get the following claim.



\vspace{0.15cm}


\begin{claim}
\label{bclth}
 (\cite{D01}) {\slshape   Let $ F( p,  n, b) \overset{def}{=} \max \limits_{e \in \mathcal{E}}  \min \limits_{R  \in \mathcal{BCL}( \gamma, b, n) }  \Pr \limits_{\mathbf{r} \leftarrow R }[f_e (\mathbf{r})=0]$. Then $$ F( p,  n, b) \leq \frac{1}{ p \cdot (1+ \gamma)^b} = 2^{ \log \frac{1}{p} - \Theta (\gamma b  ) }.$$


  }

\end{claim}

 In other words, if $b$ is ``high enough'' (i.e., $b \gg \frac{1}{ \gamma}  \log \frac{1}{p}$), then the imperfect source attacker $  \mathcal{A} $ can  force any $p$-sparse event to happen with  probability very close to  $1$.



Now let's come back to our lemma. Define the function $f_e: \{0, 1\}^n \rightarrow  \{0, 1\}$  as follows.

\begin{equation}
f_e( \mathbf{r}) =  \left\{
\begin{aligned}
1, & ~~ if ~ \mathbf{r} \in G;  \nonumber\\
0, & ~~ otherwise. \nonumber\\
\end{aligned}
\right.
\end{equation}



Then from  the above claim, we have $ \min \limits_{ R \in \mathcal{BCL}( \gamma, b, n)} \Pr \limits_{  \mathbf{r} \leftarrow R } \ [ f_e ( \mathbf{r} )= 0]  \leq  \frac{1}{ \frac{|G |}{ 2^n  } \cdot (1+ \gamma)^b}$.



Thus, there exists a $( \gamma, b, n)-$BCL distribution $R_0$  such that  $$ \Pr \limits_{  \mathbf{r} \leftarrow R_0 } \ [ f_e( \mathbf{r} )= 0] =
\min \limits_{ R \in \mathcal{BCL}( \gamma, b, n)} \Pr \limits_{  \mathbf{r} \leftarrow R } \ [ f_e( \mathbf{r} )= 0]  \leq  \frac{1}{\frac{|G |}{ 2^n  } \cdot (1+ \gamma)^b}.$$  Hence,
 $$ \Pr  \limits_{ \mathbf{r}  \leftarrow R_0  } [\mathbf{r} \in G] = \Pr \limits_{ \mathbf{r}  \leftarrow R_0  } [  f_e ( \mathbf{r}  )= 1] \geq 1- \frac{1}{\frac{|G |}{ 2^n  }   \cdot (1+ \gamma)^b}. $$
 $$ \Pr \limits_{\mathbf{r} \leftarrow R_0 } [ \mathbf{r}  \in  B   ]  \leq \Pr \limits_{\mathbf{r} \leftarrow R_0 }[f_e (\mathbf{r}  ) =0]  \leq  \frac{1}{ \frac{|G |}{ 2^n  }   \cdot (1+ \gamma)^b}. $$
Correspondingly, $ \Pr  \limits_{ \mathbf{r}  \leftarrow R_0  } [\mathbf{r} \in G] - \Pr \limits_{\mathbf{r} \leftarrow R_0 } [ \mathbf{r}  \in  B   ]  \geq
1-  \frac{2}{\frac{|G |}{ 2^n  }   \cdot (1+ \gamma)^b} \geq  1-  \frac{2^{t+2} }{  (1+\gamma)^b}$.
Therefore,   $  \mathcal{BCL}(\gamma, b, n)$ is $(t,     1-  \frac{2^{t+2} }{  (1+ \gamma)^b})-$separable.


Let $ \frac{2^{t+2} }{  (1+\gamma)^b} \leq \frac{1}{2}$, that is,  $ b \geq \frac{t+3}{ \log (1+ \gamma)}$.
 Therefore, $  \mathcal{BCL}(\gamma, b, n)$ is $(t,  \frac{1}{2})-$separable  if  $ b \geq \frac{t+3}{ \log (1+ \gamma)}$.


\end{proof}

\section{Non-Implication for the SV source}\label{app:SV}

%\mypar{(Non-)Implications for the SV source.}
We observe that Theorem \ref{imdp} cannot be applied to the SV source, as $\mathcal{SV}(\gamma, n)$ is only $(t, \delta)$-expressive for $\delta =   \frac{\gamma}{2^{t+1}}$, which means that $2^t \delta =O(\gamma)$. In contrast, to apply Theorem \ref{imdp} we need $2^t \delta\ge \Omega(\rho \varepsilon)$. Thus, to have any hope, we need, $\rho = O(\gamma/\varepsilon)$, but this violates our pre-condition (used in the proof) that
$\rho \ge 1/(8\varepsilon)$. In fact, a simple reworking of the proof of Theorem \ref{imdp} (omitted) can be used to show that  if there exists a  $(   \mathcal{SV}( \gamma, n ), \varepsilon)-$differentially private and $( U_n,  \rho)$-accurate mechanism for the Hammimg weight queries, then $  \rho  > \frac{ \gamma}{  32 \cdot \varepsilon}= \Omega( \frac{\gamma}{\varepsilon})$.

%
%\vspace{0.15cm}

%\begin{corollary}
%\label{imsv}
%{\slshape   If there exists a  $(   \mathcal{SV}( \gamma, n ), \varepsilon)-$differentially private and $( %U_n ,  \rho)$-accurate mechanism for the Hammimg weight queries, then $  \rho   > \frac{ \gamma}{  32 e %\cdot \varepsilon}= \Omega( \frac{\gamma}{\varepsilon})$.

 %  }

%\end{corollary}

%\begin{proof}

%The proof is similar to that of Theorem \ref{imdp}. Please see the Appendix for details.







%\rightline { $\Box$ }

%\end{proof}

%\vspace{0.15cm}


Unfortunately, this implication that we get is quite weak, because we can get a  {\slshape  stronger}  result,
even if $  \mathcal{R}_n $ consists only of the uniform distribution $ U_n$.
We present this well known folklore result for completeness.

\begin{lemma}
\label{uni}
 {\slshape  Assume that the mechanism  $M$ is  $(U_n,  \varepsilon)-$differentially private and $( U_n , \rho )$-accurate for the Hammimg weight queries.  Then $ \rho \geq \frac{1}{e+1} \cdot \frac{1}{\varepsilon } = \Omega(\frac{1}{\varepsilon })$.     }

\end{lemma}

\begin{proof}  For any $D, D' \in \mathcal{D}$, let $  \beta \overset{def}{=}  \frac{ \mathbb{E}_{\mathbf{r} \leftarrow R} [M(D', \mathbf{r})]  }{  \mathbb{E}_{\mathbf{r} \leftarrow R} [M(D,  \mathbf{r})]   }$.  From Definition \ref{uti}, we have $  \beta  \geq \frac{ wt(D') - \rho  }{wt(D)  +  \rho}$.
By Definition \ref{dp},
% and the fact that  $  1+ \varepsilon \leq e^{\varepsilon}$,
we obtain
$$  \beta = \frac{\sum _z  z \Pr \limits_{\mathbf{r} \leftarrow  R}[M(D', \mathbf{r}) =z ]}{\sum _z z \Pr \limits_{\mathbf{r} \leftarrow  R}[M(D,  \mathbf{r}) =z] }  \leq \frac{ \sum _z  z e^{ \varepsilon  \cdot \Delta(D, D') }  \Pr \limits_{\mathbf{r} \leftarrow  R}[ M(D,  \mathbf{r}) =z  ] }{ \sum _z  z \Pr \limits_{\mathbf{r} \leftarrow  R}[ M(D, \mathbf{r}) =z  ]  } = e^{ \varepsilon  \cdot \Delta(D, D')}. $$
Therefore, $$ \frac{ wt(D') - \rho  }{wt(D)  +  \rho} \leq   e^{ \varepsilon  \cdot \Delta(D, D')}.$$
 Take a specific $D$  such that   $wt(D) = 0$. Let $Ball(D,\alpha) = \{D': \Delta(D,D')\le \alpha\}$.
 Then
 $$  \forall D' \in Ball\left(D, \frac{1}{  \varepsilon }\right) \Rightarrow \frac{wt(D')- \rho}{ \rho} \leq e^{  \varepsilon \cdot \Delta(D, D')  } \leq e \Rightarrow \rho \geq \frac{1}{e+1} wt(D').$$
 Taking $D'$ such that $wt(D') =  \frac{1}{\varepsilon }$, we get   $\rho \geq \frac{1}{e+1} \cdot \frac{1}{\varepsilon } $.

% \rightline { $\Box$ }
\end{proof}


   Thus, our technique  cannot yield any results for the $\gamma$-SV source, which we even didn't already know for the uniform distribution.
   Of course, this is not surprising, because Dodis et al. \cite{DLMV12} have  shown  that we can get  $(   \mathcal{SV}( \gamma, n ), \varepsilon)-$differentially private and $( \mathcal{SV}( \gamma, n ),  \rho)$-accurate mechanism for all counting queries (including the Hamming weight queries), where  $\rho = poly_{1/(1-\gamma)}( \frac{1}{ \varepsilon}) \\ \gg  \frac{1}{ \varepsilon}$ and $poly_{1/(1-\gamma)}(x)$ denotes a polynomial whose degree and coefficients are fixed (and rather large) functions of $1/(1-\gamma)$.

% \noindent\textbf{Corollary  5.5.}\   {\slshape  If    $  1-  \frac{2^{t+1} }{  (1+ \gamma)^b} >  \sqrt{e} -1$ and $ 2^t \geq 16  \varepsilon   \rho$  (  therefore,   $  b = \Omega (  \frac{1}{ \gamma} \log   \frac{32 \varepsilon \rho}{ 2- \sqrt{e}}  )$), then no $( \varepsilon, \mathcal{BCL}(\gamma, b, n)   )-$differentially private and $( \rho,  \mathcal{U} )$-accurate mechanism exists for $ \mathcal{Q}_1$.          }



% \begin{proof}  From  $  1-  \frac{2^{t+1} }{  (1+ \gamma)^b} >  \sqrt{e} -1$ and $ 2^t \geq 4 \varepsilon \cdot 4 \rho$, we  get
%that $ ( 2- \sqrt{e}) \cdot 2^{ \frac{\gamma b}{\ln 2}} \geq ( 2- \sqrt{e}) \cdot (1+ \gamma)^b > 2^{t+1} \geq 8 \varepsilon \cdot 4 \rho$, that is,  $ \gamma b >  \log \frac{8   \varepsilon \cdot 4 \rho }{ 2- \sqrt{e}} \cdot  \ln 2$. Therefore, $ b = \Omega (  \frac{1}{ \gamma} \log   \frac{8 \varepsilon \cdot 4 \rho}{ 2- \sqrt{e}}  )$.

%Since the  $  \mathcal{BCL}(\gamma, b, n)$ is $(t,  1-  \frac{2^{t+1} }{  (1+ \gamma)^b})-$separable, we obtain that
%no $( \varepsilon , \mathcal{BCL}(\gamma, b, n)   )-$differentially private and $( \rho,  \mathcal{U} )$-accurate mechanism exists for $ \mathcal{Q}_1$.

%\end{proof}


% \noindent\textbf{Remark 2.}\
% Since the source $\mathcal{BCL}(\gamma, b, n)$ is  $(\frac{2^n}{4N},    1-  \frac{2}{\frac{N}{ 2^n  }   \cdot (1+ \gamma)^b})-$expressive,  Let $1-  \frac{2}{\frac{N}{ 2^n  }   \cdot (1+ \gamma)^b}= \sqrt{e}-1$, then $\frac{2^n}{4N}= \frac{(2-\sqrt{e})(1+ \gamma)^b }{8}$.
%Let  $\frac{(2-\sqrt{e})(1+ \gamma)^b }{8}= O(\varepsilon \rho)$. Then $b= O(  \frac{\varepsilon \rho}{\gamma})$. Therefore, from Theorem 2,
%we can also conclude Theorem 3.





\section{$\gamma$-biased half-space source}\label{app:BHS}

\begin{definition}
   Given $S  \subset \{0, 1\}^n$ of size $ |S| = 2^{n-1}$, and  $ 0 \leq \gamma < 1$,
the  distribution  $R \overset{def}{=} H_S(\gamma, n)$ over $ \{0, 1\}^n  $   is defined as

\begin{equation}
  \left\{
\begin{aligned}
\Pr[R= \mathbf{r}] = (1+  \gamma) \cdot 2^{-n}, & ~~ if ~ \mathbf{r} \in S; \nonumber\\
\Pr[R= \mathbf{r}] = (1-  \gamma) \cdot 2^{-n}, & ~~ otherwise. \nonumber\\
\end{aligned}
\right.
\end{equation}

The $\gamma$-biased half-space source $\mathcal{H}(\gamma, n)$  is defined as  $$\mathcal{H}(\gamma, n) \overset{def}{=} \{ H_S(\gamma, n)  \mid  S \subseteq \{0, 1\}^n ~and~ |S| = 2^{n-1} \}.     $$


\end{definition}

\begin{claim}
\label{his}


(\cite{DOPS04,RVW04}) {\slshape  For any $n \in \mathbb{Z}^+$ and $  0 \leq \gamma < 1$, $ \mathcal{H}(\gamma, n)  \subset \mathcal{SV}(\gamma, n)$.  }

\end{claim}

Using this claim, \cite{DOPS04} used the $\gamma$-biased half-space sources to establish their impossibility results for the $\gamma$-SV sources.

\ignore{

\begin{lemma}
\label{natural}
 ~\\ {\slshape   (1)  $  \mathcal{SV}(\gamma, n)$ is $(t,   \frac{\gamma  }{2^{t+1}} )-$separable.\\
  (2)  $\mathcal{B}lock(k, m, n)$ is  $(t,   \frac{ 2^{m-k} -1  }{ 2^{t+1} \cdot (2^{m-k} +1)} )-$separable.       }
\end{lemma}

\begin{proof}
~\\
(1)  In proving Lemma \ref{natural} (1), we use a notion called  the  $ \gamma-$biased  half-space source \cite{DOPS04},    which was  implicitly defined by
\cite{RVW04}.


\begin{definition}

   Given $S  \subset \{0, 1\}^n$ of size $ |S| = 2^{n-1}$, and  $ 0 \leq \gamma < 1$,
the  distribution  $R \overset{def}{=} H_S(\gamma, n  )$ over $ \{0, 1\}^n  $   is defined as

\begin{equation}
  \left\{
\begin{aligned}
\Pr[R= \mathbf{r}] = (1+  \gamma) \cdot 2^{-n}, & ~~ if ~ \mathbf{r} \in S; \nonumber\\
\Pr[R= \mathbf{r}] = (1-  \gamma) \cdot 2^{-n}, & ~~ otherwise. \nonumber\\
\end{aligned}
\right.
\end{equation}

The $\gamma$-biased half-space source $\mathcal{H}(\gamma, n)$  is defined as  $$\mathcal{H}(\gamma, n) \overset{def}{=} \{ H_S(\gamma, n)  \mid  S \subseteq \{0, 1\}^n ~and~ |S| = 2^{n-1} \}.     $$


\end{definition}





\begin{claim}
\label{his}


(\cite{DOPS04,RVW04}) {\slshape  For any $n \in \mathbb{Z}^+$ and $  0 \leq \gamma < 1$, $ \mathcal{H}(\gamma, n)  \subset \mathcal{SV}(\gamma, n)$.  }

\end{claim}

Therefore, we only  need to choose a subset $S$ such that $ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]  \geq   \frac{\gamma}{2^{t+1}} $.




$  \mathbf{Case~1}$:  Suppose that $|G| \leq 2^{n-1}$.   Then $  |B| + 2^{n-1} \leq |G| + 2^{n-1}  \leq 2^n$.
Choose a set $S \subset \{0, 1\}^n$ of size $|S|= 2^{n-1}$ such that $G \subseteq S$ and $ B \cap S = \emptyset$.  Then $$ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]  = \frac{ 1+ \gamma}{2^n} \cdot |G| - \frac{ 1- \gamma}{2^n} \cdot |B|   =   \frac{|G|-|B|  }{2^n  }   +  \gamma \cdot  \frac{|G|+|B|  }{2^n } \geq  \gamma \cdot \frac{ 2^{n-t}}{2^n} = \frac{\gamma}{2^t}.$$



$  \mathbf{Case~2}$:  Now assume that $|G| > 2^{n-1}$. Pick any $S \subset \{0, 1\}^n$ of size   $|S|= 2^{n-1}$ such that $S \subset G$. Then
$ |S| = | \{0, 1\}^n  \setminus  S | \geq | G \setminus  S |$.
%$$ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]= \frac{1+ \gamma}{2^n} \cdot |S| + \frac{1- \gamma}{2^n} \cdot |G \setminus  S| - \frac{1- \gamma}{2^n} \cdot |B|  $
 \begin{align*}
&\Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B] = \frac{1+ \gamma}{2^n} \cdot |S| + \frac{1- \gamma}{2^n} \cdot |G \setminus  S| - \frac{1- \gamma}{2^n} \cdot |B|\\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~= \frac{1- \gamma}{2^n} \cdot ( \frac{1+ \gamma }{ 1- \gamma}   \cdot |S| + | G \setminus  S  | -   |B|) \\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~= \frac{1- \gamma}{2^n} \cdot (  |S| + |G \setminus  S| -  |B| + \frac{2 \gamma}{1- \gamma}  \cdot |S|  )  \\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~\geq \frac{1- \gamma}{2^n} \cdot [ ( |S| + |G \setminus  S|) -  |B| +  \frac{ \gamma}{1- \gamma}  \cdot  (|S|+  |G \setminus  S|   )]\\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = \frac{1- \gamma}{2^n} \cdot [ ( |G| -  |B| ) +  \frac{ \gamma}{1- \gamma}  \cdot  |G|]\\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~\geq   \frac{1- \gamma}{2^n} \cdot \frac{ \gamma}{1- \gamma}  \cdot  2^{n-t-1} \\&
~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = \frac{\gamma}{2^{t+1}}.
\end{align*}

\vspace{0.15cm}


(2) We'll use the following claim of \cite{DOPS04}, which is indeed a generalization of Lemma 2 in \cite{RVW04}.

\begin{claim}   (\cite{DOPS04})
\label{svblock}
 {\slshape  For any $S  \subset \{0, 1\}^n$ of size $ |S| = 2^{n-1}$,  $ 0 \leq \gamma < 1$, and $m \in \mathbb{Z}^+$, where $n/m$ is an integer, the distribution $H_S(\gamma, n)$ is an $n$-bit $(m,  m- \log \frac{1+ \gamma}{1-\gamma})$-block distribution.

  }

\end{claim}

\ignore{
\begin{proof}  From Definition \ref{block},  we only need to prove that     $ \mathbf{H}_\infty (R_i \mid \overline{R_i} = s) \geq m -\log \frac{1+ \gamma}{1-\gamma}$  for all
  $i \in [m/n]$
and  $s \in \{0, 1\}^{n-m}$.  Since

\begin{align*}
& \max \limits_{x \in \{0, 1\}^m }  \Pr[R_i=x \mid \overline{R_i} = s]  = \max \limits_{x \in \{0, 1\}^m }   \frac{\Pr[R_i=x \wedge \overline{R_i} = s] }{ \Pr[\overline{R_i} = s] }  \leq \frac{\frac{1+ \gamma}{2^n}}{ \frac{1 - \gamma}{2^n} \cdot 2^m }=\frac{1+ \gamma}{1 - \gamma} \cdot 2^{-m},\\&
\end{align*}
we get $ \mathbf{H}_\infty (R_i \mid \overline{R_i} = s) = -\log  \max \limits_{x \in \{0, 1\}^m }  \Pr[R_i=x \mid \overline{R_i} = s] \geq m -\log \frac{1+ \gamma}{1-\gamma}.$

\end{proof}
}

Let $ \gamma =  \frac{2^{m-k} -1}{2^{m-k} +1}$, then $k = m- \log \frac{1+ \gamma}{1-\gamma}$.  Hence, we only  need to choose a subset $S$ such that $ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]  \geq   \frac{\gamma}{2^{t+1}} $, where  $\gamma =  \frac{2^{m-k} -1}{2^{m-k} +1}$.
 By the proof of (1), there exists a subset $S$ such that $ \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in G  ] - \Pr  \limits_{ \mathbf{r} \leftarrow H_S( \gamma, n) }[ \mathbf{r} \in B]  \geq   \frac{\gamma}{2^{t+1}} $.




\end{proof}









\ignore{


In the following, we prove Corollary \ref{imsv}:


\begin{proof}
Assume that there exists
such a mechanism $M$.   Let $\mathcal{D}' \overset{def}{=} \{D \mid wt(D) \leq 4 \rho\}$.  Denote

\begin{equation}
  \textsf{Trunc} (x) \overset{def}{=}   \left\{
\begin{aligned}
0, & ~~ if ~ x < 0; \nonumber\\
x, & ~~ if ~  x \in \{0, 1, \ldots, 4 \rho\}; \nonumber\\
4\rho, & ~~ otherwise.
\end{aligned}
\right.
\end{equation}

 For any $D \in \mathcal{D}'$, define the truncated mechanism $ M' \overset{def}{=}  \textsf{Trunc} (M)$ by $ M'(D, \mathbf{r}) \overset{def}{=} \textsf{Trunc} (  M(D, \mathbf{r}))$.  Since for every $D \in \mathcal{D}'$, we have $wt(D) \in   \{0, 1, \ldots, 4 \rho\}$,
 $M'$ still has $(U_n, \rho)-$utility on $\mathcal{D}'$. Additionally, from Definition \ref{dp}, it's straightforward that $M'$ is  ($\mathcal{R}_n, \varepsilon$)-differentially private on $\mathcal{D}'$. In the following, we only consider the truncated mechanism $ M' $ on $\mathcal{D}'$.


 \begin{claim}
   {\slshape   For databases $D, D' \in  \mathcal{D}'$  and any distribution $R \in  \mathcal{SV}( \gamma, b, n)$,
  denote $ f(R) \overset{def}{=} M'(D,  R  )$ and $ g(R) \overset{def}{=} M'(D',  R )$.   If $ \Delta (D, D')  =   \frac{\gamma  }{  e \cdot \varepsilon \cdot 2^{t+2}}$, then  $\Pr \limits_{ \mathbf{r} \leftarrow U_n }[ f(  \mathbf{r}) \neq g(  \mathbf{r}) ] < \frac{1}{ 2^t}$.}

 \end{claim}

 \begin{proof}

 Since $M'$ is    $( \mathcal{R}_n,     \varepsilon)$-differentially private,
we get $ \textsf{RD}(f(R),  g(R)  ) \leq \varepsilon \cdot  \Delta (D, D') \leq   \frac{\gamma  }{  e   \cdot 2^{t+2}}$. Hence,
$$\textsf{SD}(f(R),  g(R)  ) \leq e^{   \frac{\gamma  }{  e   \cdot 2^{t+2}} } -1 < e \cdot     \frac{\gamma  }{  e   \cdot 2^{t+2}} = \frac{\gamma  }{    2^{t+2}}.$$
The last  inequality holds according to the fact:  $e^{ x  } -1 < e \cdot x$   for $ 0 < x \leq 1$.  Actually,  let $g_1(x) \overset{def}{=} e^{ x  } -1$ and $g_2(x) \overset{def}{=}  e \cdot x$. Let $ g'_1(x)  $ (resp.  $ g'_2(x)  $) denote the  derivative with respect to $x$ of the  function $g_1(x)$ (resp.  $g_1(x)$). Then  $g'_1(x) = e^x$ and $g'_2(x) =e$. When $ 0 \leq x \leq 1$, $g'_1(x) \leq g'_2(x)$. In addition, $ g_1(0)=g_2(0)$.  Therefore, $0 < x \leq 1$ implies $e^{ x  } -1 < e \cdot x$.



 Since $ \mathcal{R}_n$  is $(t,  \frac{\gamma  }{2^{t+2}} )-$expressive, we conclude that    $\Pr \limits_{ \mathbf{r} \leftarrow U_n }[ f(  \mathbf{r}) \neq g(  \mathbf{r}) ] < \frac{1}{ 2^t}$.

%\rightline { $\Box$ }

\end{proof}

For simplicity, denote   $ i^* \overset{def}{=}  \frac{4 e \varepsilon \rho \cdot 2^{t+2}}{ \gamma}$.   Consider  a sequence of databases $D_0, D_1, \cdots, D_{ i^* }$ such that
$wt( D_i) =   \frac{\gamma  }{  e \cdot \varepsilon \cdot 2^{t+2}}  \cdot i   $ and $\Delta (D_i, D_{i+1}) =   \frac{\gamma  }{  e \cdot \varepsilon \cdot 2^{t+2}}$.  Denote $f_i(R) \overset{def}{=} M'(D_i,  R  )$.
From the above Claim, we get that $ \Pr \limits_{ \mathbf{r} \leftarrow U_n}   [  f_i (\mathbf{r} ) \neq  f_{i+1} (\mathbf{r} ) ]   <  \frac{1}{ 2^t  }~ for ~all~ i=0, 1, \ldots, i^*-1$.

 Hence, $$ \Pr \limits_{ \mathbf{r} \leftarrow U_n}   [  f_0 (\mathbf{r} ) \neq  f_{ i^* } (\mathbf{r} ) ] \leq \sum \limits_{i=0}^{ i^* -1}  \Pr \limits_{ \mathbf{r} \leftarrow U_n}   [  f_i (\mathbf{r} ) \neq  f_{i+1} (\mathbf{r} ) ].$$   Therefore,
$$ \Pr \limits_{ \mathbf{r} \leftarrow U_n}   [  f_i (\mathbf{r} ) \neq  f_{i+1} (\mathbf{r} ) ]   <  \frac{1}{ 2^t  }~ for ~all~ i=0, 1, \ldots, i^*-1
\Rightarrow
 \Pr \limits_{ \mathbf{r} \leftarrow U_n}   [  f_0 (\mathbf{r} ) \neq  f_{  i^* } (\mathbf{r} ) ] <  \frac{4 e \varepsilon \rho \cdot 2^{t+2}}{ \gamma}  \cdot \frac{1}{2^t} =  \frac{16 e \varepsilon \rho }{ \gamma}.$$
Let $\alpha \overset{def}{=}   \mathbb{E}_{ \mathbf{r} \leftarrow  U_n} [ f_{i^* } (\mathbf{r}  ) - f_0 (\mathbf{r}  )   ]$.   From $\rho$-security (even on $U_n $), we get  that
$ \alpha \geq (4 \rho - \rho) - \rho =2 \rho $ and  $  \alpha  \leq \Pr \limits_{ \mathbf{r} \leftarrow U_n  } [f_0 (\mathbf{r})  \neq   f_{i^*} (\mathbf{r}  ) ] \cdot [\max (f_{i^* }) -  \min (f_0 )] <     \frac{16 e \varepsilon \rho }{ \gamma}  \cdot 4 \rho$.
Correspondingly, $  2 \rho \leq \alpha <  \frac{16 e \varepsilon \rho }{ \gamma}  \cdot 4 \rho $.  Hence, $ \rho > \frac{ \gamma}{  32 e \cdot \varepsilon}$.





%\rightline { $\Box$ }

\end{proof}


}


}



}



\end{document}
